比赛 noip 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 __完全平方数 最终得分 100
用户昵称 Lethur 运行时间 3.429 s
代码语言 C++ 内存使用 18.75 MiB
提交时间 2016-11-04 20:06:06
显示代码纯文本
    #include<cstdio>  
    #include<iostream>  
    #include<cmath>  
    using namespace std;  
    const int m=100000007;  
    int n,x,l;  
    long long ans;  
    int p[5000005],a[350000],b[350000];  
    int main()  
    {  
    	freopen("xnumber.in","r",stdin);
    	freopen("xnumber.out","w",stdout);
        ans=1;  
        cin>>n;  
        x=int(sqrt(n));  
        for(int i=2;i<=x;i++)  
        if(p[i]==0)  
        {  
            int y=n/i;  
            for(int j=2;j<=y;j++) p[i*j]=1;  
        }  
        for(int i=2;i<=n;i++)  
        if(p[i]==0)  
        {  
            l++;  
            a[l]=i;  
        }  
        for(int i=1;i<=l;i++)  
        {  
            x=n;  
            while(x/a[i]>0)  
            {  
                x=x/a[i];  
                b[i]=b[i]+x;  
            }  
        }  
        for(int i=1;i<=l;i++)  
        {  
            if(b[i]%2==1) b[i]--;  
            for(int j=1;j<=b[i];j++) ans=(ans*a[i])%m;  
        }  
        cout<<ans<<endl;  
        return 0;  
    }