bzoj2721 / P1445 [Violet]樱花

P1445 [Violet]樱花

显然$x,y>n$

那么我们可以设$a=n!,y=a+t(t>0)$

再对原式通分一下$a(a+t)+ax=x(a+t)$

$a^{2}+at+ax=ax+tx$

$x=a^{2}/t+a$

$x=(n!)^{2}/t+n!$

再根据唯一分解定理

$(n!)^{2}=q_{1}^{p_{1}}*q_{2}^{p_{2}}*q_{3}^{p_{3}}*......*q_{m}^{p_{m}}$

将$(n!)^{2}$分解质因数一下

最后乘法原理套上去

end.

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define re register

 using namespace std;

 #define N 1000002

 const int mod=1e9+;

 int n,v[N],pri[N],cct,ans=;

 int main(){

     scanf("%d",&n);

     for(re int i=;i<=n;++i){

         if(!v[i]) v[i]=pri[++cct]=i;

         for(re int j=;j<=cct;++j){

             if(pri[j]>i||pri[j]*i>n) break;

             v[pri[j]*i]=pri[j];

         }

     }

     for(re int i=;i<=cct;++i){

         long long cnt=;

         for(re int j=n;j;j/=pri[i]) cnt+=j/pri[i];

         cnt=cnt<<|;

         ans=1ll*ans*cnt%mod;

     }printf("%d",ans);

     return ;

 }