这道题把我坑了好久......
原因竟是CRT忘了取正数！
题意：求
指数太大了，首先用欧拉定理取模。
由于模数是质数所以不用加上phi(p)
然后发现phi(p)过大，不能lucas，但是它是个square free，可以分解质因数然后lucas然后CRT。
然后就没有然后了......模板套来套去......
注意CRT的结果可能是负数，要取正。
#include <cstdio>
#include <algorithm>
#define say(a) printf(#a); printf(" = %lld \n", a) typedef long long LL;
const int N = ;
const LL MO = ;
const LL prime[] = {, , , }; int T;
LL n, G;
LL nn[][N], inv[][N], invn[][N], aa[]; inline LL qpow(LL a, LL b, LL c) {
LL ans = ;
while(b) {
if(b & ) {
ans = ans * a % c;
}
a = a * a % c;
b = b >> ;
}
return ans;
}
LL C(int a, int b) {
return nn[T][a] * invn[T][b] % prime[T] * invn[T][a - b] % prime[T];
}
LL lucas(int a, int b) {
if(!b) {
return ;
}
return C(a % prime[T], b % prime[T]) * lucas(a / prime[T], b / prime[T]) % prime[T];
}
LL exgcd(LL a, LL b, LL &x, LL &y) {
if(!b) {
x = ;
y = ;
return a;
}
LL g = exgcd(b, a % b, x, y);
std::swap(x, y);
y -= (a / b) * x;
return g;
} inline void prework(int h) {
inv[h][] = ;
LL p = prime[h];
for(int i = ; i < p; i++) {
inv[h][i] = (p - p / i) * inv[h][p % i] % p;
}
nn[h][] = ;
invn[h][] = ;
for(int i = ; i < p; i++) {
nn[h][i] = nn[h][i - ] * i % p;
invn[h][i] = invn[h][i - ] * inv[h][i] % p;
}
return;
} inline LL CRT() { LL M = MO - , ans = , b, t;
for(int i = ; i < ; i++) {
LL m = M / prime[i];
exgcd(m, prime[i], t, b);
t = (t % M + M) % M;
ans += aa[i] * m % M * t % M;
ans %= M;
} return ans;
} int main() { scanf("%lld%lld", &n, &G);
if(G == MO) {
printf("");
return ;
}
for(int i = ; i < ; i++) {
prework(i);
} for(T = ; T < ; T++) {
for(int i = ; i * i <= n; i++) {
if(n % i) {
continue;
}
aa[T] += lucas(n, i);
aa[T] %= prime[T];
if(i * i < n) {
aa[T] += lucas(n, n / i);
aa[T] %= prime[T];
}
}
//printf("aa[%d] = %lld \n", T, aa[T]);
} LL ans = CRT();
//printf("ans = %lld \n", ans); ans = qpow(G, ans, MO);
printf("%lld\n", ans);
return ;
}
AC代码