題目描述：

一個數如果是另一個整數的完全平方，那么我們就稱這個數為完全平方數（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的完全平方?！据斎胼敵鰳永忉?】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、快速冪（這里沒加），多乘幾次再取模。
證明：
　　　　　　奇個數的的質因數一定可去，且留著也沒用。