网站建设软件公司,网站定位代码,信贷客户精准获客,建设银行网站登录密码题目大意#xff1a;给定第一个数M#xff0c;后面有n的数#xff0c;求解a[1]^a[2]^a[3]^…..%m的解 思路#xff1a;开始的时候并不知道从哪里下手#xff0c;一开始收到前面某题除4的印象#xff0c;然后一直对4取余#xff0c;知道a[1],计算后发现那一套只适用于求解… 题目大意给定第一个数M后面有n的数求解a[1]^a[2]^a[3]^…..%m的解 思路开始的时候并不知道从哪里下手一开始收到前面某题除4的印象然后一直对4取余知道a[1],计算后发现那一套只适用于求解最后一位的情况苦思敏想不得其解最后不得不去找答案原来涉及到剩余系定理即a^ba^(b%phi[M])phi[M])(phi[M]为M的欧拉函数) 如此一来只是不断调用求解函数到最后一个即可。 Code #include iostream
#include cstdio
#include cmath
#include string
#include cstring
#include algorithm
using namespace std;typedef long long ll;
const int N10005;
int n,m;
int a[15],phi[N];void tab()
{for (int i2;iN;i) phi[i]0;phi[1]1;for (int i2;iN;i){if (phi[i]) continue;for (int ji;jN;ji){if (!phi[j]) phi[j]j;phi[j]phi[j]/i*(i-1);}}
}
int pow_mod(int a,int n,int m)
{int ans1;while (n){if (n%21) ansans*a%m;n/2;aa*a%m;}return ans;
}
int cal(int i,int m)
{//coutbugendl;if (in-1) return a[i]%m;int tcal(i1,phi[m]);//coutbugendl;return pow_mod(a[i],tphi[m],m);
}
int main()
{tab();int ca1;while (cinm){scanf(%d,n);for (int i0;in;i)scanf(%d,a[i]);int anscal(0,m);printf(Case #%d: %d\n,ca,ans);}
}
