题意:取x个不大于n的数相乘出一个最大的完全平方数!
这里点击打开链接有某大牛的题解,我就不再累赘了。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define LL long long
#define N 10000000
#define mod 1000000007
bool flag[N+5];
int cnt,prime[N/10];
LL num[N+5];
void Prime()
{
memset(flag,false,sizeof(flag));
cnt=0;
for(int i=2;i<=N;i++) //O(n)的算法取素数
{
if(flag[i])continue;
for(int j=2*i;j<=N;j+=i)flag[j]=true;
prime[cnt++]=i;
}
}
int getsum(int n,int p) //这里可以到得n!里面有多少个素数因子p
{
int ans=0;
while(n)
{
ans+=n/p;
n/=p;
}
return ans;
}
int pow(LL x,int n) //快速幂相乘
{
LL ans=1;
while(n)
{
if(n&1)ans=ans*x%mod;
x=x*x%mod;
n>>=1;
}
return ans;
}
int main()
{
//freopen("a.txt","r",stdin);
num[0]=1;
for(int i=1;i<=N;i++)num[i]=num[i-1]*i%mod; //求阶乘
Prime();
int n;
while(scanf("%d",&n)&&n)
{
LL ret=1;
for(int i=0;i<cnt&&prime[i]<=n;i++)
{
int x=getsum(n,prime[i]);
if(x&1)ret=ret*prime[i]%mod;(
}
int ans=num[n]*pow(ret,mod-2)%mod; //这里用到了费马小定理,既x^(mod-1))%mod=1
printf("%d\n",ans);
}
return 0;
}