记录编号	337898	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	__完全平方数	最终得分	100
用户昵称	Lethur	是否通过	通过
代码语言	C++	运行时间	2.655 s
提交时间	2016-11-04 22:02:37	内存使用	22.06 MiB

    #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;  
    }