TIOJ-1353

發表於 更新於 Disqus：

在歷史上，鴻門宴是齣很大的事件，鴻門宴上，雖不乏美酒佳肴，但卻暗藏殺機，項羽的亞父范增
一直主張殺掉劉邦，在酒宴上，三次舉起所佩玉玦，一再示意項羽發令，但項羽卻猶豫不決，
默然不應。范增召項莊舞劍為酒宴助興，趁機殺掉劉邦，項伯為保護劉邦，也撥劍起舞，掩護了劉邦，
在危急關頭，劉邦部下樊噲帶劍擁盾闖入軍門，怒目直視項羽，項羽見此人氣度不凡，只好問來者是何人，
當得知是劉邦的部將時，即命賜酒，樊噲立而飲之，樊噲還乘機說了一些劉邦的好話，項羽無言以對，劉邦乘機一走了之。
離開之後，劉邦心有不甘，所以假裝釋懷好意、盡釋前嫌，向項羽陪了不是，又邀請楚軍各大將領來參加他所舉辦的『綠門宴』，以殺掉他們的等級將領。

劉邦聽說楚軍將領的分級是按照令牌的數量來決定，而令牌上則有一些數字，很神奇的是除了1以外沒有小於他的數字能整除他，而將領們可以利用那些數字、大於等於一的次方以及乘法，來定義自己鎧甲上的號碼。
如：某A有2與3的令牌，他的鎧甲就有可能是$2^5 \times 3 = 96$

今天將領們按照其鎧甲上的號碼入座，劉邦發現他們鎧甲上的數字剛好形成一個公差為1的等差數列。
如果能殺掉他們等級最高的將領，楚軍必會動搖，而漢軍就有機可乘了！你能幫助他嗎？

輸入兩個數字$a, b$，代表第一個人與最後一個人的號碼，輸出持有最多令牌的人的令牌數量與號碼。

$a, b\le 10^6$，有多筆測資

被包裝了一下。

除了1以外沒有小於他的數字能整除他

代表令牌上的數字為質數，令牌數量為質因數的數量。
所以這問題是給$L,R$，問區間$[L,R]$中含最多質因數的數字(因為公差為1，所以是從整個區間找)。

範圍很大，對於每個數字都用根號去找不太好。
但總值域不大(只有$10^6$)，所以可以用埃氏篩，埃氏篩可以記錄每個數字的所有因數或質因數，就可以在$O(nlogn)$的時間建表。

至於詢問，如果詢問數量有點多，那得用線段樹配二分搜，然而我偷懶想賭賭看詢問數很少，從執行時間來看的確很少。
複雜度:$O(nlogn+nT)$，$T$為測資數量。

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
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
/*-----------------------------------------------------------------------------------------------------*/

const int N = 1e6 + 25;
int cnt[N];

signed main() {
	EmiliaMyWife

	for(int i = 2; i < N; i++) {
		if(cnt[i])
			continue;
		for(int j = i; j < N; j += i) {
			cnt[j]++;
		}
	}
	int a, b;
	while(cin >> a >> b) {
		int mx = 0, num = 1;
		for(int j = a; j <= b; j++) {
			if(mx < cnt[j])
				mx = cnt[j], num = j;
		}
		cout << num << ' ' << mx << '\n';
	}

	return 0;
}