UVA 294 约数 Divisors

前言：

我没开long long在VJ上竟然过了！！！

题面翻译

给定 $n$ 个数值区间 $[l,r]$，求出每个区间内约数个数最大的数，并按照以下格式输出：

Between [l] and [r], [maxn_num] has a maximum of [maxn_divisor] divisors.
1

样例输入：

3
1 10
1000 1000
999999900 1000000000
1
2
3
4

样例输出：

Between 1 and 10, 6 has a maximum of 4 divisors.
Between 1000 and 1000, 1000 has a maximum of 16 divisors.
Between 999999900 and 1000000000, 999999924 has a maximum of 192 divisors.
1
2
3

对于 $100\%$ 的数据：

$1\le l_i<r_i\le 10^{10}$，$1\le r-l\le 10^4$

题目描述

PDF

输入格式

输出格式

样例 #1

样例输入 #1

3
1 10
1000 1000
999999900 1000000000
1
2
3
4

样例输出 #1

Between 1 and 10, 6 has a maximum of 4 divisors.
Between 1000 and 1000, 1000 has a maximum of 16 divisors.
Between 999999900 and 1000000000, 999999924 has a maximum of 192 divisors.
1
2
3

分析：

因为题目给的数据范围$1\le r-l\le 10^4$不太大，所以我们直接暴力枚举就可以啦。（代码有详细分析）

代码：

#include

using namespace std;

int aa(int n)//分解质因数（返回值为n的约数个数）
{
	int ans=1;
	
	for(int i=2;i<=sqrt(n);i++)
	{
		if(n%i==0)//找到了n的质因子
		{
			int res=1;
			
			while(n%i==0)
			{
				res++;
				
				n/=i;
			}
			
			ans*=res;
		}
	}
	
	if(n>1)//如果还有，乘以二
	{
		ans*=2;
	}
	
	return ans;
}

int n;

int l,r;

int maxx=-100;

int k;

int main()
{
	cin>>n;
	
	while(n--)
	{
		maxx=-100;
		
		cin>>l>>r;
		
		k=0;
		
		for(int i=l;i<=r;i++)//在区间中枚举
		{
			if(aa(i)>maxx)//只要i的质因数个数比maxx大
			{
				maxx=aa(i);//更新maxx
				
				k=i;//更新下标
			}
		}
		
		printf("Between %d and %d, %d has a maximum of %d divisors.\n",l,r,k,maxx);//按要求输出
	}
	
	return 0;
}
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

结束啦~~~