题意
n 个数选若干个使其相乘为完全平方数，问完全平方数最大是多少。
思路
完全就是两个相同的数相乘，所以我们可以对于 ≤n 的数分解质因子，然后每个质因子取偶数个，将他们相乘就行
细节
相乘时要用快速幂，记得开 long long
普通的分解质因子不管怎么样都是 TLE 的用我以下代码只能拿到 85 分
#include<bits/stdc++.h>
using namespace std;
const int Mod=1e8+7;
long long cnt,n,ans=1;
int nex[5000005],prime[5000005],s[5000005];
bool vis[5000005];
long long fz(long long a, long long b, long long c)
{
if(b==0) return 1;
if(b==1) return a%c;
long long t=fz(a,b/2,c)%c;
return (((t*t)%c)*(b%2==0?1:a%c))%c;
}
int main()
{
cin>>n;
vis[1]=1;
for(int i=1;i<=n;++i)
{
if(!vis[i]) nex[i]=i,prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=n;++j)
{
nex[i*prime[j]]=prime[j];
vis[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
nex[1]=0;
for(int i=1;i<=n;++i)
{
int x=i;
while(nex[x])
{
s[nex[x]]++;
x/=nex[x];
}
}
for(int i=1;i<=n;++i) ans*=fz(i,s[i]/2*2,Mod),ans%=Mod;
cout<<ans;
return 0;
}
时间复杂度
<O(n log n) 可过此题