\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\)
解法
約数系包除原理に近い考え．
まず gcd \(d\) を全探索して， \(d\) の倍数になる個数を数える． 丁度 \(d\) に対して調べるのが本問の答えだが， 簡単のために 最大とは限らない公約数 \(d\) に対しても調べて， それを利用して求める．
\(f(d) := \#\set{A \in K^{N}}{d = gcd(A)}\),
\(g(d) := \#\set{A \in K^{N}}{d \in cd(A)} = \#\set{A \in K^{N}}{d \leq_{div} gcd(A)}\)
\(g(d) := \#\set{A \in K^{N}}{d \in cd(A)} = \#\set{A \in K^{N}}{d \leq_{div} gcd(A)}\)
とする．ここで， \(cd(A)\) は \(A\) の公約数全体の集合．
\(\# g(d) = (\lfloor \frac{K}{d} \rfloor)^{N} \)
となる． また， \(d \leq_{div} gcd(A)\) であることは， \(gcd(A) = d, 2d, 3d, \cdots \) であることと同値なので，
\(g(d) = f(d) + f(2d) + f(3d) + \cdots\)
と同値． よって， \(f(d) = g(d) - f(2d) - f(3d) - \cdots\) となるから，\(d\) の大きい方から \(f(d)\) が求まる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,k;
cin >> n >> k;
mint ans = 0;
drep1(d,k){
f[d] = mint(k/d).pow(n);
for(ll i = 2*d; i <= k; i += d){
f[d] -= f[i];
}
ans += f[d] * d;
}
cout << ans.val() << endl;
return 0;
}
