大家好，又见面了，我是全栈君。
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);
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115980.html原文链接：https://javaforall.net
