完全平方数题解

完全平方数

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

---

首先我们要知道一个性质：对于一个完全平方数，其分解质因数后每个质因数的次幂为偶数，所以我们将 $1$ 到 $n$ 的数分解质因数后，将质因数个数为奇数的 $-1$(相当于去掉了若干个互不相同的质数)。然后就可以得到一个最大的完全平方数。
因为将每个数质因数分解的复杂度比较大，所以我们从质数开刀，记录有多少个数包含他，显然 $1-n$ 中有 $n÷prim{e}_j$ 个数有 $prim{e}_j$ 这个质数，包含 $2$ 次的为 $n÷prim{e}_j÷prim{e}_j$ 个。这个可以用肥肠煎蛋的分配律来考虑。接下来放上代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5000007;
const int pyz=1e8+7;
int n,m;
inline int read()
{char c;int res,flag=0;while((c=getchar())>'9'||c<'0') if(c=='-')flag=1;res=c-'0';while((c=getchar())>='0'&&c<='9') res=(res<<3)+(res<<1)+c-'0';return flag?-res:res;
}
bool is[N];
int ans,tmp,cnt[N],prime[N];
inline int ksm(int s,int t)
{int res=1;while(t){if(t&1) res=(ll)res*s%pyz;s=(ll)s*s%pyz;t>>=1;}return res;
}
int main()
{n=read();for(int i=2;i<=n;++i){if(!is[i]) prime[++prime[0]]=i;for(int j=1;j<=prime[0]&&i*prime[j]<=n;++j){is[i*prime[j]]=1;if(!(i%prime[j])) break;}}for(int i=1;i<=prime[0];++i){tmp=n;while(tmp/prime[i]>0){cnt[i]+=tmp/prime[i];tmp/=prime[i];}}ans=1;for(int i=1;i<=prime[0];++i){if(cnt[i]&1) cnt[i]--;ans=(ll)ans*ksm(prime[i],cnt[i])%pyz;}printf("%d",ans);
}