TopCoder

呵呵好喔
取出水壺 打開瓶蓋 操課後飲水 500cc 少量多次 喝水 喝水不複誦

User's AC Ratio

81.8% (18/22)

Submission's AC Ratio

25.7% (36/140)

Tags

Description

有個吐鈔機,他產生(吐)鈔票的機制非常特別。他有無限多個閘口排成一列,從左到右分別是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的原料進入吐鈔機的前提下,請問透過調配吐鈔機的裁剪係數而能達到的驚喜感最大值為何?

Input Format

本題含有多筆測資。
第一行包含兩個正整數$N_{max}\leq 10^ 7, Q\leq 10^ 4$,分別代表每次詢問時n的上限以及詢問個數。
接下來Q行中,每行都包含一個正整數$n\leq N_{max}$,代表每次只能放入大小為n的原料。

子任務(測資) 額外限制 分數
1 (0~2) $N_{max} \leq 10^ 4$ 20
2 (3~5) $Q \leq 10$ 20
3 (6~8) 無限制 60

Output Format

對於每筆詢問,請輸出驚喜感的最大值。

Sample Input 1

6 2
4
6

Sample Output 1

18
257

Hints

n=4時最大值發生在裁剪係數為2的狀況。
n=6時最大值發生在裁剪係數為1的狀況。

Problem Source

Problem set / Description by Paupière

Subtasks

No. Testdata Range Score
1 0~2 20
2 3~5 20
3 6~8 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 2
4 1000 65536 262144 2
5 1000 65536 262144 2
6 1500 65536 262144 3
7 1500 65536 262144 3
8 1500 65536 262144 3