狄利克雷卷积
CF757E
Link
很巧妙，可以很明显发现：
\[f_{r+1}(n)=\sum_{d\mid n} f_r(n)
\]
而
\[f_0(n)=2^{\Omega(n)}
\]
则\(f\)函数的值与质因数的确切值无关。而发现 \(f\) 为积性函数。那么可以对于每一个质因数，和他分别的指数，预处理出形如 \(f_r(p^q)\) 的形式的函数值，再分解质因数计算即可。
代码：
#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int R = 1e6 + 5;
const int LG = 22;
const int Md = 1e9 + 7;
ll ans[R][LG];
int lp[R];
vector<int> prim;
void init(void) {ans[0][0] = 1;for (int i = 1; i <= LG; ++i) ans[0][i] = 2;for (int i = 1; i < R; ++i) {ans[i][0] = 1;for (int j = 1; j < LG; ++j) ans[i][j] = (ans[i][j - 1] + ans[i - 1][j]) % Md;}
}
void get_primes(void) {for (int i = 2; i < R; ++i) {if (!lp[i]) {lp[i] = i;prim.push_back(i);}for (auto p : prim) {if (i * p >= R) break;lp[i * p] = p;if (i % p == 0) break;}}
}
int main() {FASTIO;init();get_primes();int q;cin >> q;while (q--) {int n, r;cin >> r >> n;ll ret = 1;while (true) {if (n == 1) break;int cnt = 0, lpp = lp[n];while (n % lpp == 0) {n /= lpp;++cnt;}ret = (ret * ans[r][cnt]) % Md;}cout << ret << '\n';}return 0;
}
莫比乌斯反演
LG P1829
Link
恶心的推式子！！！
\[\begin{aligned}\sum_{i=1}^{n}\sum_{j=1}^{m} lcm(i,j) &=\sum_{d=1}^{\min(n,m)} \sum_{i=1}^n \sum_{j=1}^m \frac{ij}{d}[\gcd(i,j)=d] \\
&=\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} ij[
\gcd(i,j)=1] \\
&=\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}i\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} j[
\gcd(i,j)=1] \\
&=\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}i\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} j \times \epsilon(\gcd(i,j)) \\
&=\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}i\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} j \sum_{x \mid \gcd(i,j)}\mu(x) \\
&=\sum_{d=1}^{\min(n,m)}d\sum_{x=1}^{\min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)}\mu(x)\sum_{i=1}^{\lfloor \frac{n}{dx} \rfloor}i\sum_{j=1}^{\lfloor \frac{m}{dx} \rfloor} j \\
\end{aligned}
\]
然后就可以套两层整除分块做了。
代码：
#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 1e7 + 5;
const int Md = 20101009;
#define int ll
vector<int> prime;
int a, b, d;
int lp[N], miu[N], sum[N];
ll rev = (Md + 1) / 2;
ll get(int n, int m) {return n * (n + 1) % Md * rev % Md * m % Md * (m + 1) % Md * rev % Md;
}
ll calc(int n, int m) {if (n > m) swap(n, m);int l = 1, r = 0, ans = 0;for (; l <= min(n, m); l = r + 1) {r = min(n / (n / l), m / (m / l));ans += (sum[r] - sum[l - 1]) * get(n / l, m / l) % Md;ans += Md;ans %= Md;}return ans;
}
ll calc1(int n, int m) {if (n > m) swap(n, m);int l = 1, r = 0, ans = 0;for (; l <= min(n, m); l = r + 1) {r = min(n / (n / l), m / (m / l));ans += (l + r) * rev % Md * (r - l + 1) % Md * calc(n / l, m / l) % Md;ans += Md;ans %= Md;}return ans;
}
void get(void) {miu[1] = 1;for (int i = 2; i < N; ++i) {if (!lp[i]) {lp[i] = i;miu[i] = -1;prime.push_back(i);}for (auto p : prime) {if (i * p >= N) break;lp[i * p] = p;if (i % p == 0) {miu[i * p] = 0;break;}elsemiu[i * p] = -miu[i];}}for (int i = 1; i < N; ++i)sum[i] = (sum[i - 1] + miu[i] * i % Md * i % Md + Md) % Md;
}
signed main() {FASTIO;get();int n, m;cin >> n >> m;cout << calc1(n, m) << '\n';return 0;
}