正整數的冪次
想必大家都知道 \(2^4=4^2,3^2=9^1,3^6=27^2\) 等正整數的冪次之間相等的關係。你有沒有想過底數和指數在某個範圍以內的正整數冪次到底有幾種呢?
給定正整數 \(n,m\),定義集合 \(S=\{x^y\ |\ x,y\in\mathbb{N},1\le x\le n,1\le y\le m\}\)。
問題很簡單,請計算 \(|S|\bmod 998244353\)。
Input
輸入只有一行,這行輸入兩個正整數 \(n,m\ (1\le n,m\le 10^{14})\)。
Output
輸出一個整數,代表 \(|S|\bmod 998244353\)。
Constraints
第 \(1\) 組測資:\(1\le n,m\le 10\)。(\(1\%\))
第 \(2\) 組測資:\(1\le n,m\le 500\)。(\(7\%\))
第 \(3\) 組測資:\(1\le n,m\le 10^6\)。(\(22\%\))
第 \(4\) 組測資:\(1\le n\le 10^6\)。(\(43\%\))
第 \(5\) 組測資:無特別限制。(\(27\%\))
Sample Input 1
4 4
Sample Output 1
11
Sample Input 2
48763 45510
Sample Output 2
216698900
Comments