正文

【BZOJ 2721】 2721: [Violet 5]樱花 （筛）

IP云
IP云V管理员/0 阅读
12/02
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

2721: [Violet 5]樱花

Time Limit: 5 Sec  Memory Limit: 128 MB
Submit: 599  Solved: 354

Description

Input

Output

Sample Input

Sample Output

HINT

Source

interviewstreet--EQUATIONS

【分析】

之前推出来然后几天直接打然后把$n!^2$的约数记成$n^2$的约数也是醉、、

先通分。

则$(x+y)*n!=x*y$

设$g=gcd(x,y)$

则$(x'+y')*n!=x'*y'*g$

显然$gcd(x'+y',x')=gcd(x'+y',y')=1$

所以$x'*y'|n!$ 、$(x'+y')|g$

设$g=k(x'+y')$，则$n!=x'*y'*k$

枚举$n！$的互质约数对$(x',y')$,则k就确定了，所以只是问$n！$的互质约数对的个数。

把$n！$分解质因数，假设$n!=p1^{r1}+p2^{r2}+...+pn^{rn}$

$f[i]$表示前i个p对答案的贡献，则$f[i]=f[i-1]*(2*ri+1)$

则答案就等于$\Pi (2*ri+1)$,也就是$(n!)^{2}$的约数个数。【别人好像直接推出这个。。。？ 

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<vector>

 using namespace std;

 #define Maxn 1000010

 #define Mod 1000000007

 #define LL long long

 int n;

 int pri[Maxn],pl,mn[Maxn];

 bool vis[Maxn];

 void init()

 {

     memset(vis,,sizeof(vis));

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

     {

         if(!vis[i]) pri[++pl]=i,mn[i]=i;

         for(int j=;j<=pl;j++)

         {

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

             vis[i*pri[j]]=;

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

             if(i%pri[j]==) break;

         }

     }

 }

 int sm[Maxn];

 void cal(int x)

 {

     if(x==) return;

     sm[mn[x]]++;

     cal(x/mn[x]);

 }

 int main()

 {

     int ans=;

     scanf("%d",&n);

     init();

     memset(sm,,sizeof(sm));

     for(int i=;i<=n;i++) cal(i);

     for(int i=;i<=n;i++) if(sm[i]) ans=1LL*ans*(*sm[i]+)%Mod;

     printf("%d\n",ans);

     return ;

 }

2017-04-24 14:22:56

相关阅读

目录[+]