Sol
好神仙的题目。。
一开始就直接莫比乌斯反演然后就 (GG) 了
orz 题解
permui
枚举 (n)，就是求 (sum_{i=1}^{n}S(i,m))
其中(S(n,m)=sum _{i=1}^mvarphi (ni))
设 (n=prod_{i}p_i^{c_i})
设 (y=prod _{i=1} p_i^{c_i-1})，(w=prod _{i=1}p_j)
那么
[egin{aligned}
S(n,m)&=ysum _{i=1}^mvarphi (wi) \
&=ysum _{i=1}^mvarphi (frac{w}{gcd(i,w)})varphi (i)gcd(i,w) \
&=ysum _{i=1}^mvarphi (frac{w}{gcd(i,w)})varphi (i)sum _{e|gcd(i,w)}varphi (e) \
&=ysum _{i=1}^mvarphi (i)sum _{e|gcd(i,w)}varphi (frac{w}{e}) \
&=ysum _{i=1}^mvarphi (i)sum _{e|i,e|w}varphi (frac{w}{e}) \
&=ysum _{e|w} varphi (frac{w}{e})S(e,lfloorfrac{m}{e}
floor) \
end{aligned}
]
运用了 (n=sum _{d|n}varphi (d)) 去掉了 (gcd)
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod(1e9 + 7);
const int maxn(1e6 + 5);
const int blk(80);
inline void Inc(int &x, int y) {
if ((x += y) >= mod) x -= mod;
}
int pr[maxn], phi[maxn], tot, d, id1[maxn], id2[maxn], idx, m, ans, sphi[maxn], low[maxn];
bitset <maxn> ispr;
map <int, int> s[maxn];
# define ID(x) ((x) <= d ? id1[x] : id2[m / (x)])
int Sumphi(int x) {
if (x < maxn) return phi[x];
if (sphi[ID(x)]) return sphi[ID(x)];
register int ans = (ll)(x + 1) * x / 2 % mod, i, j;
for (i = 2; i <= x; i = j + 1) j = x / (x / i), Inc(ans, mod - (ll)Sumphi(x / i) * (j - i + 1) % mod);
return sphi[ID(x)] = ans;
}
int Calc(int n, int v) {
if (!v || !n) return 0;
if (n == 1) return Sumphi(v);
if (v == 1) return (phi[n] - phi[n - 1] + mod) % mod;
if (s[n].count(v)) return s[n][v];
register int i, j, ret, y = 1, w = 1, x, cnt, e, dv[30];
for (cnt = 0, x = n; x > 1; ) {
w *= low[x], dv[++cnt] = low[x], x /= low[x];
while (low[x] == dv[cnt]) y *= low[x], x /= low[x];
}
for (ret = 0, i = (1 << cnt) - 1; ~i; --i) {
for (e = 1, j = 0; j < cnt; ++j) if (i >> j & 1) e *= dv[j + 1];
Inc(ret, (ll)(phi[w / e] - phi[w / e - 1] + mod) * Calc(e, v / e) % mod);
}
return s[n][v] = (ll)ret * y % mod;
}
int main() {
register int i, j, n;
phi[1] = 1, ispr[1] = 1;
for (i = 2; i < maxn; ++i) {
if (!ispr[i]) pr[++tot] = i, phi[i] = i - 1, low[i] = i;
for (j = 1; j <= tot && i * pr[j] < maxn; ++j) {
ispr[i * pr[j]] = 1;
if (i % pr[j]) phi[i * pr[j]] = phi[i] * (pr[j] - 1), low[i * pr[j]] = pr[j];
else {
phi[i * pr[j]] = phi[i] * pr[j], low[i * pr[j]] = low[i];
break;
}
}
}
for (i = 1; i < maxn; ++i) Inc(phi[i], phi[i - 1]);
scanf("%d%d", &n, &m);
for (d = sqrt(m), i = 1; i <= m; i = j + 1) {
j = m / (m / i);
(m / i <= d) ? id1[m / i] = ++idx : id2[j] = ++idx;
}
for (i = 1; i <= n; ++i) Inc(ans, Calc(i, m));
printf("%d
", ans);
return 0;
}