关键词:数学-数论  打表 相关题目:[HAOI2007]反素数

题目描述

    对于任何正整数xx,其约数的个数记作g(x)g(x)。例如g(1)=1g(1)=1g(6)=4g(6)=4。     如果某个正整数xx满足:undefined$     0<i<x0<i<x,则称xx为反质数。例如,整数 等都是反质数。

现在给定一个数NN,你能求出不超过NN的最大的反质数么?

输入输出格式

输入格式:     一个数

输出格式:     不超过N的最大的反质数。

解决方案

    如果我们设 pp 为指数,kk 为指数的话,那么如果一个数xx 可以被分成如下形式。     x=i=1npikix=\prod_{i=1}^{n}{p_i^{k_i}} 。     那么 xx 的因数个数就是 i=1nki+1\prod_{i=1}^{n}{k_i+1} 。     如果设 pip_i 严格递增,并且 ki=0k_i=0 也算在内,则如果 kx<kyk_x<k_y 并且 x<yx<y ,那么显然这个数不可能是反素数,因为交换 kxk_xkyk_y 会更好。     所以当 pip_i 递增时 kik_i 是递减的,这个数xx 才可能是反素数。     所以我们可以据此搜索。     因为前10个素数的积=6023507490>2×109=6023507490>2 \times 10^9 ,所以最多用到10个素数,手动打素数表即可。

洛谷P1463 题解 -----by钟梓俊

AC代码

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
#include<cstdio>
int n,f[70]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,
1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,
50400,55440,83160,110880,166320,221760,277200,332640,498960,
554400,665280,720720,1081080,1441440,2162160,2882880,3603600,
4324320,6486480,7207200,8648640,10810800,14414400,17097280,
21621600,32432400,36756720,43243200,61261200,73513440,110270160,
122522400,147026880,183783600,245044800,294053760,367567200,
551350800,698377680,735134400,1102701600,1396755360,2095133040};
int main(){
scanf("%d",&n);
for(int i=68;i;--i)
if(f[i]<=n){
printf("%d",f[i]);
break;
}
}
/*#include<cstdio>
#include<cstring>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))
#define drep(i,a,b) for(re i=(a);i>=(b);--(i))
#define min(a,b) (a<b?a:b)
const int INF=2100000000;
int pri[20]={0,2,3,5,7,11,13,17,19,23};
int f[10000];
inline void pout(){
int cnt=0;
int maxn=f[9999]+1;
drep(i,9999,1){
if(f[i]==2139062143) continue;
if(f[i]>maxn) continue;
maxn=f[i];
printf("%d ",f[i]);
cnt++;
if(cnt%10==0) putchar('\n');
}
}
inline long long qmod(int a,int b){
long long ans=1,m=a;
while(b){
if(b&1) ans*=m;
m*=m;
b>>=1;
}
return ans;
}
inline void dfs(int i,int pr,long long res,int tim){
if(tim>10000) return ;
f[tim]=min(f[tim],res);
if(i==10) return ;
long long zql;
drep(k,pr,1){
zql=res*qmod(pri[i],k);
if(zql>INF || zql<0) continue;
dfs(i+1,k,zql,tim*(k+1));
}
}
int main(){
memset(f,127,sizeof(f));
f[1]=1;
dfs(1,30,1,1);
pout();
}打表程序*/