题目:http://acm.nyist.net/JudgeOnline/problem.php?pid=516
不能直接逐项快速幂计算。
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef long long LL;
const int N = 10000005;
const LL MOD = 1000000007;
bool prime[N];
int p[N];
int k;
LL ans,a,x;
void isprime()
{
k = 0;
int i,j;
memset(prime,true,sizeof(prime));
for(i=2; i<N; i++)
{
if(prime[i])
{
p[k++] = i;
for(j=i+i; j<N; j+=i)
{
prime[j] = false;
}
}
}
}
void quick_mod()
{
while(x)
{
if(x&1)
{
ans = ans*a%MOD;
x--;
}
x>>=1;
a=a*a%MOD;
}
}
int main()
{
int n;
isprime();
while(~scanf("%d",&n))
{
if(n==0) break;
ans = 1;
x = 0;
a = 1;
for(int i=0; p[i] <= n; i++)
{
int t = n;
int cnt = 0;
while(t)
{
cnt += t/p[i];
t /= p[i];
}
if(cnt > 1)
{
if(cnt&1) cnt--;
if(cnt == x) a = a * p[i] % MOD;
else
{
quick_mod();
x = cnt;
a = p[i];
}
}
else
{
quick_mod();
break;
}
}
printf("%lld\n",ans);
}
return 0;
}
标签:cnt,int,LL,NYOJ516,ans,include,优化,MOD From: https://blog.51cto.com/u_16146153/6388687