1437: GCD幂和
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：78
Solved：1
Description
$\sum_{i=1}^{n}{\sum_{j=1}^{n}}
[gcd(i,j)]^m~~~~mod~~~~998244353$
$gcd(i,j)$表示i和j的最大公约数
例如$gcd(2,6) = 2,gcd(3,5) = 1,gcd(6,6) =6$
30%数据 : $n\leq100,m=3\\$
50%数据 : $n\leq500,m\leq100\\$
70%数据 : $n\leq888,m\leq10^9\\$
100%数据 : $n\leq10^6,m\leq 10^9$
[gcd(i,j)]^m~~~~mod~~~~998244353$
$gcd(i,j)$表示i和j的最大公约数
例如$gcd(2,6) = 2,gcd(3,5) = 1,gcd(6,6) =6$
30%数据 : $n\leq100,m=3\\$
50%数据 : $n\leq500,m\leq100\\$
70%数据 : $n\leq888,m\leq10^9\\$
100%数据 : $n\leq10^6,m\leq 10^9$
Input
一行两个正数n,m
Output
表达式的答案
Sample Input Copy
3 2Sample Output Copy
20