古代猪文
若q = 999911659,则得出结果为0。因为n , q互质所以可以由欧拉定理得出公式: $q ^ {\sum _{d | n} C ^ d _ n} \equiv q^{\sum _ {d | n} C ^ d _ n mod 999911658}$ (mode 999911659)
所以只要能计算出${\sum _ {d | n} C ^ d _ n mod 999911658}$ 这个就能用快速幂得出答案。
可以用分解质因数的方式将999911658分成2 , 3 , 4679 , 35617这四个质数。
分别根据卢卡斯定理求和
转化回来时可以直接用中国剩余定理
因为分别求时是mod所有999911658的质因子
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 5e4 + 10 , mod = 999911659;
LL n , q;
LL jc[N] , a[5];
int pai[4] = {2 , 3 , 4679 , 35617};
LL qmi(LL a , LL b , LL p)//快速幂
{
LL ans = 1;
while (b) {
if (b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
LL C(LL n , LL d , LL m)//组合数
{
if (n < d) return 0;
return jc[n] * qmi(jc[d], m - 2, m) % m * qmi(jc[n - d], m - 2, m) % m; //费马小定理求逆元
}
LL lucas(LL n , LL d , LL m)//卢卡斯定理
{
if (n < m && d < m)
{
return C(n, d, m);
}
return C(n % m, d % m, m) * lucas(n / m, d / m, m) % m;
}
void init(LL q)//预处理出阶乘
{
jc[0] = 1;
for(int i = 1 ; i <= q ; i++)
jc[i] = jc[i - 1] * i % q;
}
LL crt()//中国剩余定理
{
LL ans = 0;
LL m = 999911658;
for(int i = 0 ; i < 4 ; i++)
{
LL mi = m / pai[i];
LL t = qmi(mi , pai[i] - 2 , pai[i]);//因为是互质所以可以用费马小定理求逆元
ans = (ans + a[i] * mi % m * t % m) % m;
}
return ans;
}
int main()
{
scanf("%lld%lld" , &n , &q);
if(q % mod == 0)
{
puts("0");
return 0;
}
for (LL k = 0; k < 4; k++)
{
LL p = pai[k];
init(p);
for (LL i = 1; i <= n / i; i++)
{
if (n % i == 0)
{
a[k] = (a[k] + lucas(n, i, p)) % p;
if (i != n / i)
a[k] = (a[k] + lucas(n, n / i, p)) % p;
}
}
}
LL x = crt(); //中国剩余定理
printf("%lld\n", qmi(q, x, mod));
return 0;
}