本文共 1347 字，大约阅读时间需要 4 分钟。

题目

思路

感谢提供了思路。和代码。

基本思路，是从 $\mathtt{d}\mathtt{p}$ 中脱胎换骨：

如果用 $f(i,j)$ 表示 $i$ 个数字、余数为 $j$ 的答案，那么对于任意 $L$ 均有 $$f(i,j)=\sum _{x=0}^{p-1}f(L,x)\times f(i-L,(j+p-x)\mathrm{m}\mathrm{o}\mathrm{d}p)$$

也就是枚举前 $L$ 个数字的余数，与剩下的余数相加。

然后我们写一个函数 $g(L,x)={\sum }_{i=0}^{p-1}f(L,i)x^i$ ，因为 $\mathtt{d}\mathtt{p}$ 转移非常像卷积。

于是我们就可以写成快速幂的形式。求的答案就是 $g^n(1,x)$ 中的某一项。

嗯？你问我怎么处理 “有一个质数” ？正难则反，减去全部是合数的情况即可。

代码

#include
   
    #include
    
     #define mod 20170408using namespace std;int n,m,p,vis[20000010],cnt,pre[2000000];long long f[210],F[210],g[210],G[210];long long c[210],x=1;void work(long long *a,long long *b,long long *d) {
       int i,j;    for(i=0; i
     
      >n>>m>>p;    F[0]=G[0]=f[1]=g[1]=1;    for(i=2; i<=m; i++) {
           f[i%p]++;       //此时的f为f[1][0--p]的值        if(!vis[i])pre[++cnt]=i;        else g[i%p]++;    //通过欧拉筛记录g[1][0--p]的值        for(j=1; pre[j]*i<=m; j++) {
               vis[pre[j]*i]=1;            if(!(i%pre[j])) break;        }    }    while(n) {
           if(n&1)            work(F,f,F),work(G,g,G);        work(f,f,f);        work(g,g,g);        n>>=1;    }    cout<<(F[0]-G[0]+mod)%mod;  //特别注意这里，学长特别提醒我了的。F[0]可能比G[0]小。    return 0;}
     
    
   

转载地址：http://lovq.baihongyu.com/