題目描述：

一個(gè)數(shù)如果是另一個(gè)整數(shù)的完全平方，那么我們就稱(chēng)這個(gè)數(shù)為完全平方數(shù)（Pefect Sqaure），也稱(chēng)平方數(shù)。小A認(rèn)為所有的平方數(shù)都是很perfect的~于是他給了小B一個(gè)任務(wù)：用任意個(gè)不大于n的不同的正整數(shù)相乘得到完全平方數(shù)，并且小A希望這個(gè)平方數(shù)越大越好。請(qǐng)你幫助小B告訴小A滿足題意的最大的完全平方數(shù)。

輸入格式：

輸出格式：

樣例輸入：

樣例17樣例29
樣例輸出：
樣例1144樣例25184
數(shù)據(jù)范圍：
對(duì)于20%的數(shù)據(jù)，0<n≤100；對(duì)于50%的數(shù)據(jù)，0<n≤5,000；對(duì)于70%的數(shù)據(jù)，0<n≤100,000；對(duì)于100%的數(shù)據(jù)，0<n≤5,000,000。
時(shí)間限制：
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！分解質(zhì)因數(shù)后將奇數(shù)的質(zhì)因子個(gè)數(shù)減一，再將所有質(zhì)因子乘起來(lái)取余即可。
優(yōu)化：
1、篩素?cái)?shù)時(shí)，搜到一半就可以停了,后面的質(zhì)數(shù)不可能因子數(shù)超過(guò)一個(gè)。
2、快速冪（這里沒(méi)加），多乘幾次再取模。
證明：
　　　　　　奇?zhèn)€數(shù)的的質(zhì)因數(shù)一定可去，且留著也沒(méi)用。