比赛 noip 评测结果 AAAAAAAAAAAAAAAAAEEE
题目名称 __完全平方数 最终得分 85
用户昵称 芬特塞林斯 运行时间 1.267 s
代码语言 C++ 内存使用 18.42 MiB
提交时间 2016-11-04 20:42:14
显示代码纯文本
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
using namespace std;

const int maxn=500001;
const int modof=100000007;
long long int array[maxn],linein[maxn],getx,ans;
long long int save1[maxn],save2[maxn];
long long int find[maxn];
long long int check;
int n;

int main()
{
	freopen("xnumber.in","r",stdin);
	freopen("xnumber.out","w",stdout);
	cin>>n;
	ans++;
	getx=sqrt(n);
	for(int i=2;i<=n;i++)
	{
		if(!linein[i])
		{
		int backi=n/i;
			for(int j=2;j<=backi;j++)
			{
				int pri=i*j;
				linein[pri]=1;		
			}	
		}
	}
	
	for(int i=2;i<=n;i++) 
	{ 
    if(linein[i]==0)  
    	{	    
        save1[++check]=i;  
    	}  
	}
	
	for(int i=1;i<=check;i++)  
    {  
        int geta=n;  
        while(geta/save1[i]>0)  
        {  
            geta=geta/save1[i];  
            save2[i]=save2[i]+geta;  
        }  
    }
    for(int i=1;i<=check;i++)  
    {  
        if(save2[i]%2==1) 
		{
		save2[i]--;  
    	}
		for(int j=1;j<=save2[i];j++) 
		{
		ans=(ans*save1[i])%modof;  
		}
	}  
    cout<<ans;
	return 0;
}