完全平方数

题目描述：

一个数如果是另一个整数的完全平方，那么我们就称这个数为完全平方数（Pefect Sqaure），也称平方数。小A认为所有的平方数都是很perfect的~于是他给了小B一个任务：用任意个不大于n的不同的正整数相乘得到完全平方数，并且小A希望这个平方数越大越好。请你帮助小B告诉小A满足题意的最大的完全平方数。

输入格式：

输出格式：

样例输入：

样例17样例29
样例输出：
样例1144样例25184
数据范围：
对于20%的数据，0<n≤100；对于50%的数据，0<n≤5,000；对于70%的数据，0<n≤100,000；对于100%的数据，0<n≤5,000,000。
时间限制：
1S
空间限制：
128M
提示：
【输入输出样例解释1】144=2×3×4×6，是12的完全平方。【输入输出样例解释2】5184=3×4×6×8×9，是72的完全平方。
 
 
 
 
 
 
 
 
 
先上代码。
#include<bits/stdc++.h>using namespace std;const int mod=100000007;int a[5000001],n,s;long long PRime[50000001],m;bool pg[5000001];void init(){cin>>n;}void prepare(){pg[1]=1;pg[2]=0;for(int i=2;i<=n/2+1;i++){if(!pg[i]){prime[++s]=1;a[s]=0;for(int j=1;j*i<=n;j++){int ll=j;a[s]++;while (ll%i==0){a[s]++;ll/=i;}pg[j*i]=1;}if (a[s]%2==1) a[s]--;// cout<<i<<" "<<a[s]<<"/n";for(int j=1;j<=a[s];j++){prime[s]*=i;if(prime[s]>20000) prime[s]=prime[s]%mod;}}}}void doit(){m=1;for(int i=1;i<=s;i++){m*=prime[i];if(m>10000){m=m%mod;}}}void print(){cout<<m;}int main(){init();prepare();doit();print();}
解析：本题比较好想，方法：将n！分解质因数后将奇数的质因子个数减一，再将所有质因子乘起来取余即可。
优化：
1、筛素数时，搜到一半就可以停了,后面的质数不可能因子数超过一个。
2、快速幂（这里没加），多乘几次再取模。
证明：
　　　　　　奇个数的的质因数一定可去，且留着也没用。