题目描述
给出N,G,求:
$$ G^{\sum_{d|N}C(N,\frac{N}{d})}\mod 999911659 $$
解题报告
老样子,附赠样例!
Input:
71723 1931
Output:
948504873
混合数论题
首先发现模数是个大质数,必然和G互质,可以用欧拉定理降幂
降幂之后难点是求指数,指数现在是
$$\sum_{d|N}C(N,\frac{N}{d}) \mod 999911658$$
然后发现模数不是质数了,什么都不好搞了
卡了一会。。观察999911658这个数,发现此数可以分解成四个互不相同的质因数并且每个数都小于40000
JeremyGuo突然激动:这不是中国剩余定理么!
插入中国剩余定理(以下内容来自
ACDreamer
):
设正整数m1,m2,..mn两两互质,方程组
有唯一解,那么唯一解可以表示为
其中
,Mi^-1是在模mi意义下的逆元。
那么对于这道题,分别求出指数模四个质数下的解,就可以分别使用Lucas定理进行计算,然后手算逆元进行合并了。
最后吐槽一下: 0.0必须特判G%999911659==0的情况,不然会无限wa!别问我为什么我也不知道%>_<%
接下来贴代码!
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
typedef long long LL;
const LL PRIME[4] = {2,3,4679,35617};
const LL INV[4] = {1, 1, 1353, 31254};
const LL ENTRYP = 999911658;
LL N, G;
LL advPow (LL a, int b, LL c) {
a %= c;
LL ret = 1;
while(b) {
if(b & 1) ret *= a, ret %= c;
a *= a;
a %= c;
b >>= 1;
}
return ret%c;
}
LL fac_stor[4][40000], inv_stor[4][40000];
LL calC(int n, int m, int P, LL * fac, LL * inv) {
if(m > n) return 0;
if(n == m || m == 0) return 1;
return fac[n]*advPow(fac[m]*fac[n-m]%P, P-2, P)%P;
}
LL lucas (int n, int m, int P, LL * fac, LL * inv) {
if(m == 0) return 1;
return lucas(n/P, m/P, P, fac, inv)*calC(n%P, m%P, P, fac, inv)%P;
}
#include <iostream>
LL sum = 0;LL ans[4];
void attachToAns (int fact) {
//printf("fact: %d\n", fact);
for(int pi = 0; pi<4; pi++) {
LL P = PRIME[pi];
ans[pi] += lucas(N, N/fact, P, fac_stor[pi], inv_stor[pi]);
ans[pi] %= PRIME[pi];
}
}
int main () {
std :: cin >> N >> G;
const LL PMOD = PRIME[0]*PRIME[1]*PRIME[2]*PRIME[3]+1;
if(G == PMOD) {puts("0"); return 0;}
for(int pi = 0; pi<4; pi++) {
fac_stor[pi][0] = 1;
for(int i = 1; i<PRIME[pi]; i++)
fac_stor[pi][i] = fac_stor[pi][i-1]*(LL)i%PRIME[pi];
}
for(int i = 1; i*i<=N; i++)
if(N % i == 0) {
attachToAns(i);
if(N/i != i) attachToAns(N/i);
}
sum = ans[0]*(ENTRYP/PRIME[0])%ENTRYP*INV[0]
+ ans[1]*(ENTRYP/PRIME[1])%ENTRYP*INV[1]
+ ans[2]*(ENTRYP/PRIME[2])%ENTRYP*INV[2]
+ ans[3]*(ENTRYP/PRIME[3])%ENTRYP*INV[3];
sum %= ENTRYP;
std :: cout << advPow(G, sum, PMOD) << '\n';
}
Join the discussion