首页 > 代码库 > bzoj2721 [Violet 5]樱花

bzoj2721 [Violet 5]樱花

2024-08-09 11:38:14   216人阅读

Description

技术分享

Input

技术分享

Output

技术分享

 

Sample Input

 

Sample Output

 

HINT

 

技术分享

 

蛋疼的推公式题……依题意1/x+1/y=1/z，令y=z+d，然后

1/x+1/(z+d)=1/z

(x+z+d)/(xz+xd)=1/z

xz+z^2+dz=xz+xd

z^2+dz=xd

x=z^2/d+z

显然x是正整数主要取决于d能整除z^2

每一个d都对应一个唯一的x，所以答案就是z^2的约数个数

即（n!）^2的约数个数

#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define mod 1000000007#define mx 1000000using namespace std;inline LL read(){    LL x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}inline void write(LL a){    if (a<0){printf("-");a=-a;}    if (a>=10)write(a/10);    putchar(a%10+‘0‘);}inline void writeln(LL a){write(a);printf("\n");}bool prime[mx+10];LL rep[mx+10];int n;LL ans=1;inline void shai(){    memset(prime,1,sizeof(prime));    prime[1]=0;    for (int i=2;i<=n;i++)    if (prime[i])    {        LL res=i;        while ((LL)n/res>0)        {            rep[i]+=(LL)n/res;            res*=i;        }        for (int j=2*i;j<=n;j+=i)            prime[j]=0;    }}int main(){    n=read();shai();    if (n==1)    {        printf("1\n");        return 0;    }    for (int i=1;i<=n;i++)        if (prime[i])        {            ans=ans*(2*rep[i]+1)%mod;        }    printf("%lld\n",ans);}

 

bzoj2721 [Violet 5]樱花


联系
我们