[YBtOJ]最多约数

106 阅读 0 评论 70 点赞

我是靠谱客的博主爱撒娇秋天，这篇文章主要介绍[YBtOJ]最多约数，现在分享给大家，希望可以做个参考。

题目传送门

一句话：给定一个正整数 $n$ ，对于所有不超过 $n$ 的正整数，找到包含约数最多的一个数。如果有多个这样的数，那么回答最小的那个。

$25 p s$

纯暴力

复制代码

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
#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
ll n,c;
ll num,maxnum=2;
int main()
{ 
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++){  
		if(i%2==0){//偶数约数一定多      
			num=2;
			for(ll j=2;j<=sqrt(i);j++){  
				if(i%j==0){                
					if(j==i/j){ 
						num++;
					}
					else if(j<i/j){        
						num+=2;
					}
					else
						break;//当j>i/j时，在上一步已被记录，所以直接break
				}
			} 
			if(num>maxnum)
				maxnum=num,c=i;
		}
	}
	if(n==1) c=1;// 特判
	printf("%lld",c); 
	return 0;
}

$42 p s$

暴力 $+$ 打表

将 $10^3$ 到 $10^6$ 用暴力挂出来，直接输出即可。~~这样得分高~~

复制代码

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
#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
ll n,c;
ll num,maxnum=2;
int main()
{ 
	scanf("%lld",&n);
	if(n>1000&&n<=1e6){
		cout<<720720<<endl;
		return 0;
	}
	for(ll i=1;i<=n;i++){  
		if(i%2==0){      
			num=2;
			for(ll j=2;j<=sqrt(i);j++){  
				if(i%j==0){                
					if(j==i/j){ 
						num++;
					}
					else if(j<i/j){        
						num+=2;
					}
					else
						break;
				}
			} 
			if(num>maxnum)
				maxnum=num,c=i;
		}
	}
	if(n==1) c=1;
	printf("%lld",c); 
	return 0;
}

$100 p s$

数学知识：一个合数的约数个数等于它所有的 质因数 的指数加一再相乘。

举个例子,若合数 $x$ $=$ $a_1^{b_1}$ $+$ $a_2^{b_2}$ $+$ $. . .$ $+$ $a_n^{b_n}$ ，则合数 $x$ 的约数个数为 $b_1+1)$ $*$ $b_2+1)$ $*$ $. . .$ $*$ $b_n+1)$ 。

知道这个就比较好做了，建一个 $p r i m e []$ 数组来存 $1$ 至 $100$ 的素数，然后 $d f s$ 随时更新最多约数和拥有最多约数的数，并且把当时搜到的数 $x$ 的素数的倍数 $y$ （有许多）一起算出来，只需将 $x$ $*$ $($ x $约数个数$ + $1)$ 即可。对于任意一个合数 $y$ ，它的约数是多个的，每遇到一个约数 $x$ ，就改变 $y$ 的约数个数，当搜到 $y$ 时，也就完成了，直接返回即可。

$M y$ $C o d e$

复制代码

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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define ll long long
using namespace std;
inline ll read()
{
	ll s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar(); 
	}
	return s*w;
}
ll n,q,cnt,p;
ll prime[200];
void dfs(ll ks,ll js,ll ysgs,ll ys)
{//ks=开始搜的数，js=结束搜的数，ysgs=约数个数，ys=约数
	if(ysgs==p&&ys<q) q=ys;
	if(ysgs>p) q=ys,p=ysgs;//随时更新
	ll t=ys*prime[ks];//把他的倍数一起算出 
	for(ll i=1;i<=js,t<=n;i++,t*=prime[ks])
		dfs(ks+1,i,ysgs*(i+1),t);//原本+新加入倍数中 
	return; //返回
}
int Prime(int k)//求素数
{
	if(k==1) return 0;
	if(k==2) return 1;
	for(int i=2;i<=sqrt(k);i++)
		if(k%i==0) return 0;
	return 1;
}
int main()
{
	n=read();
	for(int i=1;i<=100;i++)
		if(Prime(i))
			prime[++cnt]=i;//记录
	dfs(1,5000,1,1);//5000可以开的大一点，只要保证搜完即可
	printf("%lld",q);
	return 0;
}