hdu 2421 Deciphering Password(约数个数问题)

hdu 2421 Deciphering Password(约数个数问题)

大家好,又见面了,我是全栈君。

http://acm.hdu.edu.cn/showproblem.php?pid=2421

A^B 能够写成 p1^e1 * p2^e2 * …..*pk^ek。(A。B <= 1000000)

求 ∏1^3+2^3+…+(ei+1)^3 % 10007的值。


依据质因子分解定理知A = p1^a1 * p2^a2 *…..* pk^ak,那么A^B = p1^(a1*B) * p2^(a2*B) *…..*pk^(ak*B)。

那么ei = ai*B,带入上式计算。

#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
//#define LL __int64
#define LL long long
#define eps 1e-9
const double PI = acos(-1.0);
using namespace std;

const int maxn = 1000010;
const int mod = 10007;

LL A,B;
int prime[maxn];
bool flag[maxn];
LL facCnt[1010]; //由于数组开的太大,每次都须要初始化,导致TLE了几次。
int cnt;

void getPrime()
{
    memset(flag,false,sizeof(flag));
    prime[0] = 0;
    for(int i = 2; i < maxn; i++)
    {
        if(flag[i] == false)
            prime[++prime[0]] = i;
        for(int j = 1; j <= prime[0] && prime[j]*i < maxn; j++)
        {
            flag[prime[j]*i] = true;
            if(i % prime[j] == 0)
                break;
        }
    }
}

void getFac()
{
    LL tmp = A;
    cnt = 0;
    memset(facCnt,0,sizeof(facCnt));
    for(int i = 1; i <= prime[0]&&prime[i]*prime[i] <= tmp; i++)
    {
        if(tmp % prime[i] == 0)
        {
            while(tmp%prime[i]==0)
            {
                facCnt[cnt]++;
                tmp /= prime[i];
            }
            cnt++;
        }
        if(tmp == 1)
            break;
    }
    if(tmp > 1)
    {
        facCnt[cnt++] = 1;
    }
}

int main()
{
    getPrime();
    int item = 0;
    while(~scanf("%I64d %I64d",&A,&B))
    {
        getFac();
        LL ans = 1;
        for(int i = 0; i < cnt; i++)
        {
            LL s = (((facCnt[i]*B+1)*(facCnt[i]*B+2))/2 )%mod;
            s = (s*s)%mod;
            ans = (ans*s)%mod;
        }
        printf("Case %d: %I64d\n",++item,ans);
    }
}




版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115980.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • asp.net repeater_asp.net core

    asp.net repeater_asp.net coreasp.net在Repeater嵌套的Repeater中使用复选框来自森大科技官方博客http://www.cnsendblog.com/index.php/?p=109.aspx文件中:&lt;%–顶层Repeater–%&gt;&lt;asp:RepeaterID=“rptChannel”runat=“server”&gt;&lt;%#Eval(“ChannelName”…

    2022年10月13日
  • 第58章、拍照功能实现(从零开始学Android)

    第58章、拍照功能实现(从零开始学Android)Android有两种拍照方法,一种是直接调用系统的照相Intent,使用onActivityResult获取图片资源或者指定图片路径,拍照返回成功后去指定路径读取图片;一种是用SurfaceView自定义界面,添加业务个性化功能。一、第一种方法1、设计界面  (1)、布局文件  打开activity_main.xml文件。  输入以下代码: 

  • c语言图书管理系统出现的问题,C语言图书管理系统中的问题「建议收藏」

    c语言图书管理系统出现的问题,C语言图书管理系统中的问题「建议收藏」系统使用细分的功能模块c语言图书管理系统,分别在main.c文件中调用.开发环境为Win7,Netbeans8.0.2这是main.c#include#include#include#include“bmenu.h”#include“search_allinformation.h”typedefstructbookinfo{字符数[20];/*书号*/字符名称[40];/*书…

    2022年10月11日
  • 旅行者 问题_航空公司在浪费金钱,这就是旅行者的意义所在「建议收藏」

    旅行者 问题_航空公司在浪费金钱,这就是旅行者的意义所在「建议收藏」旅行者问题(WanttoreceiveBuy/Sell/Holdinyourinbox?Signuphere.)(是否希望在收件箱中收到购买/出售/持有?在这里注册。)WelcometoBuy/Sell/Hold,Marker’sweeklynewsletterthat’s100%businessintelligenceand0%invest…

  • “word在试图打开文件时遇到错误”解决办法,亲测可用

    “word在试图打开文件时遇到错误”解决办法,亲测可用打开word文档时,出现以下报错:解决办法:步骤一:步骤二:步骤三:步骤四:步骤五:步骤六:步骤七:步骤八:点击【确定】即可。…

  • linux云服务器上安装node[通俗易懂]

    linux云服务器上安装node[通俗易懂]云服务器上搭建nodejs前言第一步:下载wget第二步:下载nodejs功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能,丰富你的文章UML图表FLowchart流程图导出与导入导出导入前言这篇是记录搭建nodejs过程的一篇文章,同时也希望能够帮到跟我一样对linux零基础的同学们。第一

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号