vjudge上题目链接：Huge Mods
附上截图：
题意不难理解，因为指数的范围太大，所以我就想是不是需要用求幂大法： A % C = A% C ( B > phi(C) ) 呢？后来发现确实需要用到，而且因为它有很多重指数，所以需要 dfs，深搜到最后一层后才返回，每次向上一层返回用求幂公式处理好的指数，然后本层用同样的原理去处理好当前层取模的值，并向上一层返回。欧拉函数预处理即可，这题的结束也有点卡人，我是用输入挂来处理的。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M = ; int phi[M] = {,,};
inline void init(int n = M - ) {
for(int i = ; i <= n; ++i)
if(!phi[i])
for(int j = i; j <= n; j += i) {
if(!phi[j]) phi[j] = j;
phi[j] = phi[j] / i *(i - );
}
} #include<cctype>
inline int read(int &x) {
x = ;
char ch = getchar();
while(!isdigit(ch) && ch != '#') ch = getchar();
if(ch == '#') return ;
while(isdigit(ch)) {
x = x * + (ch - '');
ch = getchar();
}
return ;
} int quick_mod(int a, int b, int m) {
int res = ;
while(b) {
if(b & ) res = res * a % m;
a = a * a % m;
b >>= ;
}
return res;
} int m,n,a[]; // id 为当前层的数组下标，mod 为当前层进行取模的模数，
// 由求幂公式可知 mod 每次向下一层传参时是传当前层的 mod 的欧拉函数，也就是 phi[mod] 的值
// dfs 向上一层返回用求幂公式处理好的指数，更多的参看代码了
int dfs(int id, int mod) {
if(id == n) {
if(a[id] > mod) return a[id] % mod + mod;
else return a[id];
}
int pow = dfs(id + , phi[mod]); int mul = , c = a[id], num = pow; // 因为忽略了 c <= mod 这个判断导致中间数据溢出，害我 TLE 了数次，T 得不明真相，
// 还在想是不是复杂度算错了，害得我一步步来痛苦地去调试 T.T
while(num && mul <= mod && c <= mod) {
if(num & ) mul *= c;
c *= c;
num >>= ;
}
if(num && (mul > mod || c > mod)) return quick_mod(a[id], pow, mod) + mod;
else return mul;
} int main() {
int Case = ;
init();
while(read(m)) {
read(n);
for(int i = ; i <= n; ++i)
read(a[i]);
printf("Case #%d: %d\n",++Case, dfs(,m) % m);
}
return ;
}
好久没做数论题了，果然很爽的感觉！虽然很难，虽然我还有 n 多的 XX 定理不会，不过我不会放弃这个如此吸引人的数学分支的，想当初搞 ACM 有很大原因也是因为她~