若j能整除i，则f[j]能整除f[i]

题目就变成了求约数个数和、约数的平方和

因为f[2]=1,所以奇数还要加上2的贡献

 

#include
     
      #include
      
       using namespace std;#define N 10000001typedef long long LL;const int mod=1000000007;bool vis[N];int p[664581];int t[N],c[N];int s[N],e[N];int main(){    int cnt=0;    t[1]=1;    s[1]=1;    for(int i=2;i
       
        =N) break;            vis[i*p[j]]=true;            if(i%p[j]==0)            {                t[i*p[j]]=((LL)t[i]*p[j]%mod*p[j]%mod+c[i])%mod;                c[i*p[j]]=c[i];                s[i*p[j]]=s[i]/(e[i]+1)*(e[i]+2);                e[i*p[j]]=e[i]+1;                break;            }            t[i*p[j]]=((LL)t[i]*((LL)p[j]*p[j]+1%mod))%mod;            c[i*p[j]]=t[i];            s[i*p[j]]=s[i]<<1;            e[i*p[j]]=1;        }    }    int ans1=0,ans2=0;    int Q;    int Qi,A,B,C;    scanf("%d",&Q);    scanf("%d%d%d%d",&Qi,&A,&B,&C);    while(Q--)    {        ans1+= Qi&1;        ans1+=s[Qi];        ans1-= ans1>=mod ? mod : 0;        ans2+=(Qi&1)<<2;        ans2+=t[Qi];        ans2-= ans2>=mod ? mod : 0;         Qi=((LL)Qi*A+B)%+C+1;    }    cout<
        
         <<'\n'<