題目大意：給定第一個數(shù)M，后面有n的數(shù)，求解a[1]^a[2]^a[3]^…..%m的解

?

思路：開始的時候并不知道從哪里下手，一開始收到前面某題除4的印象，然后一直對4取余，知道a[1],計算后發(fā)現(xiàn)那一套只適用于求解最后一位的情況，苦思敏想不得其解，最后不得不去找答案，原來涉及到剩余系定理，即a^b=a^(b%phi[M])+phi[M])(phi[M]為M的歐拉函數(shù)) 如此一來，只是不斷調(diào)用求解函數(shù)到最后一個即可。

?

Code：

?

#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> using namespace std;typedef long long ll; const int N=10005; int n,m; int a[15],phi[N];void tab() {for (int i=2;i<=N;i++) phi[i]=0;phi[1]=1;for (int i=2;i<=N;i++){if (phi[i]) continue;for (int j=i;j<N;j+=i){if (!phi[j]) phi[j]=j;phi[j]=phi[j]/i*(i-1);}} } int pow_mod(int a,int n,int m) {int ans=1;while (n){if (n%2==1) ans=ans*a%m;n/=2;a=a*a%m;}return ans; } int cal(int i,int m) {//cout<<"bug"<<endl;if (i==n-1) return a[i]%m;int t=cal(i+1,phi[m]);//cout<<"bug"<<endl;return pow_mod(a[i],t+phi[m],m); } int main() {tab();int ca=1;while (cin>>m){scanf("%d",&n);for (int i=0;i<n;i++)scanf("%d",&a[i]);int ans=cal(0,m);printf("Case #%d: %d\n",ca++,ans);} }

總結(jié)

以上是生活随笔為你收集整理的uva 10692——Huge Mods的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。