原题
题意
给定一个n,然后让你从1-n中选出某些数乘起来，使得乘积最大，并且乘积必须是完全平方数
分析
首先我们预处理出来1e7以内的所有素数，并且预处理出，n在1e7以内的所有n!的结果，存在fac[n]中。
根据n!素因子分解中素数p的幂为 [n/p]+[n/(p^2)]+[n/(p^3)]+……求出所有n!素因子的幂以后，对其中每个素因子的幂的个数进行判断，如果个数为奇数，则最后的fac[n]要对除以这个素因子，将所有需要被除去的素因子乘起来存在ans中，最后因为(fac[n]/ans)%MOD，不能直接除，所以求出ans的逆元：ans^(MOD-1)，用这个结果乘以fac[n]就是最终的结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include <bits/stdc++.h>
#define MAXN 10000007
#define MOD 1000000007
#define ll long long
using namespace std;
ll prime[MAXN],fac[MAXN], tot,n;
bool notPrime[MAXN];
void getPrime() {
tot=0;
memset(notPrime, false, sizeof(notPrime));
notPrime[0] = notPrime[1] = true;
for(ll i = 2 ; i < MAXN ; ++i) {
if(!notPrime[i]) {
prime[tot++] = i;
for(int j = i << 1; j < MAXN ; j+=i) {
notPrime[j] = true;
}
}
}
fac[1]=1;
for(int i=2;i<=MAXN;i++){
fac[i]=(fac[i-1]*i)%MOD;
}
}
ll getnum(ll x){
ll now=n,sum=0;
while(now){
sum+=(now/=x);
}
return sum;
}
ll gcd(ll a,ll b){
return (b>0)?gcd(b,a%b):a;
}
ll phi(ll k)
{
ll i;
ll result = k;
ll t = (ll)sqrt(k*1.0);
for(i = 2; i <= t; i++)
{
if(k%i==0)
{
result = result/i*(i-1ll);
while(k%i==0)
k=k/i;
}
}
if(k>1ll)
result = result/k*(k-1ll);
return result;
}
ll pow_mod(ll m,ll c,ll k) {
ll b=1;
while(c>0){
if(c&1)
b=(b*m)%k;
c=c>>1 ;
m=(m*m)%k;
}
return b;
}
int main()
{
ll a;
getPrime();
while(scanf("%I64d",&n)!=EOF){
if(n==0){
break;
}
ll ans=1;
for(int i=0;i<tot;i++){
if(prime[i]>n){
break;
}
a=getnum(prime[i]);
if((a&1)==1){
ans=(prime[i]*ans)%MOD;
}
}
ans=(fac[n]*pow_mod(ans,MOD-2,MOD))%MOD;
printf("%I64d\n",ans);
}
return 0;
}
|
