題目：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; }

?

總結

以上是生活随笔為你收集整理的NYOJ516(优化)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。