TIOJ-1425

發表於 更新於 Disqus：

有個吐鈔機，他產生(吐)鈔票的機制非常特別。他有無限多個閘口排成一列，從左到右分別是2號,3號,5號,…,如此下去地依照質數由小到大的順序編號。而他需要接收一坨原料才能產生鈔票，且產生這個鈔票的結果受這個吐鈔機的「裁剪係數」x(一個正整數)影響。
具體而言，如果你將大小為n的原料丟進一裁剪係數x的吐鈔機，那麼這個吐鈔機會盡量將這坨原料盡可能切成多塊大小恰為x的原料。假設原料被切割成了s塊，那麼對於第i號閘口，如果i整除s，這個閘口就會隨機產生一個0到F之間的整數(16進制)；如果i不整除s的話，這個閘口只會產生一個數字0。而最終產生的鈔票金額，就是把閘口產生的數字反過來寫。
比如說將大小為19的原料丟進截剪係數為3的吐鈔機時，吐鈔機會先將原料切成6份。而因為2和3整除6，且其它質數都不整除6，所以只有第2號跟第3號閘口有機會產生不是0的數字。假設第2號閘口產生的數字是1，第3號閘口產生的數字是2，那麼最終產生的鈔票金額就是…0000021，也就是21。
作為吐鈔機的主人，你想要知道在給定的原料大小下，這個吐鈔機帶給你的驚喜度最高有多高(你並不在意他產生出來的鈔票金額高低)，而一個吐鈔機能帶給你的驚喜感就是他可能產生的鈔票金額種數再加上他的裁剪係數。當然，你不希望這個吐鈔機帶給你的只有超高的驚喜度以及一堆0元鈔票，所以你規定裁剪係數不能超過n。給定一個n，在要求每次一定都只能放大小為n的原料進入吐鈔機的前提下，請問透過調配吐鈔機的裁剪係數而能達到的驚喜感最大值為何？

$N\le 10^7, Q\le 10^4$

理解題意後就會發現若原料被切成$x$份，則會有$f(x)$個位置可能會產生16個數字的其中一種，那就會有$16^{f(x)}$種組合。(其中$f(x)$是$x$的質因數數量)。

也就是說，他是在問:
$$\max_{x=1}^n16^{f(\lfloor\frac{n}{x}\rfloor)}+x$$
看到向下取整不難想到可以用數論分塊在根號的時間枚舉完可能的x。(數論分塊會幫我們找出一段區間$[l, r]$使得$\lfloor\frac{n}{l}\rfloor=\lfloor\frac{n}{r}\rfloor$，然後就只要去看$16^{f(\lfloor\frac{n}{r}\rfloor)}+r)$是多少就好)

那要怎麼計算$f(x)$? 可以用線性篩配上dp。

因為線性篩中每個數字只會被篩一次，如果$x$是質數顯然$f(x)=1$，否則在用這個數字篩掉其他數字時直接把當前的 f 餵給他，假設那個數字跟$x$的最小質因數不一樣，那就把那個數字的$f$再加上1。

順便把16的次方給預處理好，注意到$10^7$以內的$f$最大只到7，所以只要用個小小的陣列就塞得下了。

至此，我們就能用$\mathcal{O}(1)$的時間檢查，總時間複雜度$\mathcal{O}(Q\sqrt N+N)$。(話說我寫完之後才發現我沒有用while(cin >> n >> q)，但題目明明說有多筆測資?)

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

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
/*--------------------------------------------------------------------------------------*/

const int N = 1e7 + 25;
char cnt[N];
vector<int> prime;
int fac[8];

signed main() { EmiliaMyWife
	prime.reserve(664699);
	for(int i = 2; i < N; i++) {
		if(!cnt[i])
			prime.push_back(i), cnt[i]++;
		for(int a : prime) {
			if(1LL * a * i >= N)
				break;
			cnt[a * i] = cnt[i];
			if(i % a == 0)
				break;
			cnt[a * i]++;
		}
	}
	fac[0] = 1;
	for(int i = 1; i < 8; i++)
		fac[i] = fac[i - 1] * 16;
	int mn, q;
	cin >> mn >> q;
	while(q--) {
		int n;
		cin >> n;
		int ans = 0;
		for(int i = 1, j; i <= n; i = j + 1) {
			int x = n / i;
			j = n / x;
			ans = max(ans, fac[cnt[x]] + j);
		}
		cout << ans << '\n';
	}
}