大家好,又见面了,我是全栈君。
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账号...