h400. 蛋糕店促銷(困難版)
Tags : Greedy 快速冪 數學
Accepted rate : 20人/22人 ( 91% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-05-18 23:24

Content

※請注意,此題為困難版,簡易版與困難版的唯一差異在於$N$與$T$的範圍。

最近蛋糕店的生意不好,為了吸引客人來光顧,蛋糕店的老闆最近在想要做一個促銷活動,活動內容大致如下。

在蛋糕店裡設置了摸彩箱,摸彩箱裡面有很多紙卡,每個紙卡上面都寫著一個正整數。而來光顧的每個客人都可以進行一次摸彩,假設客人摸彩摸到了數字$M$,他可以使用特定規則找出一個數字$K$,並且用$10M$的價格買走$K$個蛋糕,找出$K$的方法如下:

將數字$M$拆成最少$1$最多$M$個正整數,並且將這些正整數相乘,所得到的值即為$K$。

而老闆為了評估成本,要事前知道所有紙卡最多可以買走幾個蛋糕,希望你能幫助他,但由於答案可能很大,請將答案取$998244353$的餘數後再告訴老闆。

Input

輸入的第一行有一個正整數$T$($1≤T≤2×10^5$),代表老闆要問你$T$個不同紙卡。

接著有$T$行,每行有一個正整數$N$($1≤N≤2^{32}$),代表老闆問你數字$N$最多可以買走幾個蛋糕。

Output

對於每一個$N$,請輸出一行,每行有一個數字$K$,代表數字$N$最多可以買走$K$個蛋糕。

Sample Input #1
3
5
4
1
Sample Output #1
6
4
1
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (10%): 1.0s , <10M
公開 測資點#1 (10%): 1.0s , <10M
公開 測資點#2 (10%): 1.0s , <10M
公開 測資點#3 (10%): 1.0s , <10M
公開 測資點#4 (10%): 1.0s , <10M
公開 測資點#5 (10%): 1.0s , <10M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
Hint :

對於第一個數字$5$,可能的答案有

$1×1×1×1×1=1$

$1×1×1×2=2$

$1×2×2=4$

$1×1×3=3$

$2×3=6$

$1×4=4$

$5=5$

其中最大者為$6$。

 

※2022/05/18 23:24更,加強測資$N$範圍至$2^{32}$,並且重新rejudge。

Tags:
Greedy 快速冪 數學
出處:
pcsh weekly contest [管理者: Ststone1687 (Ststone) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」