为什么用%d输出p,p不是指针吗,为什么不是用%p输出,指针变量实际上是整型变量,只是用来存储地址吗?
两种都可以,取决于你希望输出的是什么
不知道你这个问题是否已经解决, 如果还没有解决的话:#define long long LL;
LL res[67][67]={0};
LL C(LL n,LL m){
if(m==0||n==m) return 1;
else if(res[n][m]!=0) return res[n][m];//记录已经计算过的C[n][m],防止重复计算
else return res[n][m]=C(n-1,m)+C(n-1,m-1)%p;//赋值并返回
}
//使用筛法得到素数表prime,注意表中最大素数不得小于n
int prime[maxn];
//计算C(n,m)%p
int C(int n,int m,int p){
int ans = 1;
//遍历不超过n的所有质数
for(int i = 0; prime[i] <= n;i++) {
//计算C(n,m)中prime[i]的指数c,cal (n,k)为n!中含质因子k的个数
int C = cal(n, prime[i]) - cal (m, prime[i]) -cal(n - m, prime[i]);
//快速幂计算prime[i]^c%p
ans = ans * binaryPow(prime[i], C,p)%p;
return ans;
int lucas(int n,int m){
if(m==0) return 1;
else return C(n%p,m%p)*Lucas(n/p,m/p)%p;
}//原理没看,代码不长可以死记,或者看书189页
示例 | n | m | p | 方法 |
---|---|---|---|---|
case1 | <=10^4 | <=10^4 | <=10^9 | 方法一 |
case2 | <=10^6 | <=10^6 | <=10^9 | 方法二 |
case3 | <=10^18 | <=10^18 | <=10^9(p是素数) | 方法四 |
方法三太长了,以后再看,一般情况下方法一就够用了。