Description

Solution

容斥原理，答案为忽略质数限制的方案数减去不含质数的方案数

然后矩阵乘法优化一下DP即可

Code

#include 
    
     #include 
     
      #include 
      
       #define N 120using namespace std;const int MOD=20170408;int n,m,p,pri[2000010],cnt[N],top;bool vis[20000010];struct info{    int A[N][N];    info(){for(int i=0;i
       
        >=1,A=A*A) if(c&1) res=res*A;    return res;}int main(){    scanf("%d%d%d",&n,&m,&p);    vis[1]=1;    for (int i=2;i<=m;i++){        if (!vis[i])pri[++top]=i;        for (int j=1;j<=top&&i*1ll*pri[j]<=m;j++){            vis[i*pri[j]]=1;            if(i%pri[j]==0)break;        }    }    for(int i=1;i<=m;++i) cnt[i%p]++;    for(int i=0;i