3768 简单的数学题
题意：给定$n, p$，求
$$
\sum_{i=1}^n \sum_{i=1}^n ij\gcd(i,j) \mod p
$$
枚举约数
$$
\sum_{d=1}^n d\sum_{i=1}^n \sum_{i=1}^n ij [\gcd(i,j)=d]
$$
将后面的提取因数
$$
\sum_{d=1}^n d^3 \sum_{i=1}^{\lfloor \frac nd \rfloor} \sum_{i=1}^{\lfloor \frac nd \rfloor} ij [\gcd(i,j)=1]
$$
将布尔式化成$\mu$
$$
\sum_{d=1}^n d^3 \sum_{i=1}^{\lfloor \frac nd \rfloor} \sum_{i=1}^{\lfloor \frac nd \rfloor} ij \sum_{k|i,k|j}\mu(k)
$$
先枚举$k$
$$
\sum_{d=1}^n d^3 \sum_{k=1}^{\lfloor \frac nd \rfloor} k^2 \mu(k) (\sum_{i=1}^{\lfloor \frac n{kd} \rfloor} i)^2
$$
设$T=kd$
$$
\sum_{T=1}^n (\sum_{i=1}^{\lfloor \frac nT \rfloor} i)^2 \sum_{d|T}d^3 (\frac Td)^2 \mu(\frac Td) \\
\sum_{T=1}^n (\sum_{i=1}^{\lfloor \frac nT \rfloor} i)^2 T^2\sum_{d|T}d \mu(\frac Td)
$$
后面是个卷积形式，根据$\mu * id = \varphi$
$$
\sum_{T=1}^n (\sum_{i=1}^{\lfloor \frac nT \rfloor} i)^2 T^2 \varphi(T)
$$
现在要求$T^2 \varphi(T)$的前缀和。不妨先设$g=id^2$
$$
(f * g)(i)=\sum_{d|i} d^2 \varphi(d) \times id^2(\frac id) \\
= \sum_{d|i} d^2 \varphi(d) \times (\frac id)^2 \\
= \sum_{d|i} i^2\varphi(d) \\
= i^2\sum_{d|i} \varphi(d) \\
= i^3
$$
则
$$
g(1)S(n)=\sum_{i=1}^n(f * g)(n) - \sum_{i=2}^n g(i)S(\lfloor \frac ni \rfloor) \
S(n)=\sum_{i=1}^n i^3 - \sum_{i=2}^n i^2 S(\lfloor \frac ni \rfloor)
$$
再由两个公式
$$
1^3+2^3+ \dots + n^3 = (1+2+ \dots + n)^2 \\
1^2+2^2+ \dots + n^2 = \frac{n(n+1)(2n+1)}{6}
$$
即可完成求解
坑：
1、$n$要运算时一定要先模，否则$10^{10} \times 10^{10}$马上爆炸
2、$2n$也要模
知识点：
1、整除分块只有$\lfloor \frac nd \rfloor$部分相同，可以用来乘
2、Dirichlet卷积运用
3、LCM和那题没搞明白的东西
4、预处理逆元免除$\log$
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL N = 8000000;
LL vis[N + 5], pri[2000000 + 5], tot;
LL phi[N + 5], nn, p, inv6, inv2;
map<LL, LL > ansphi;
LL ksm(LL a, LL b) {
LL ret = 1, bs = a;
while (b) {
if (b & 1) ret = (ret * bs) % p;
bs = (bs * bs) % p;
b >>= 1;
}
return ret;
}
LL get2(LL n) {
return n % p * (n + 1ll) % p * (2 * n % p + 1ll) % p * inv6 % p; // n % p，2 * n % p
}
LL get3(LL n) {
return n % p * (n + 1ll) % p * inv2 % p;
}
LL getphi(LL n) {
if (n <= N) return phi[n];
if (ansphi[n]) return ansphi[n];
LL ret = get3(n) * get3(n) % p;
LL l = 2;
while (l <= n) {
LL r = n / (n / l);
ret = (ret - ((get2(r) - get2(l - 1)) % p + p) % p * getphi(n / l) % p) % p;
ret = (ret + p) % p;
l = r + 1;
}
return ansphi[n] = (ret + p) % p;
}
void init() {
ms(vis, 0), ms(pri, 0), tot = 0, ms(phi, 0);
phi[1] = 1;
for (LL i = 2; i <= N; ++i) {
if (!vis[i]) pri[++tot] = i, phi[i] = i - 1ll;
for (LL j = 1; j <= tot && 1ll * pri[j] * i <= 1ll * N; ++j) {
vis[pri[j] * i] = 1;
if (i % pri[j] == 0) {
phi[i * pri[j]] = phi[i] * pri[j] % p;
break ;
} else phi[i * pri[j]] = phi[i] * phi[pri[j]] % p;
}
}
for (LL i = 2; i <= N; ++i) phi[i] = (phi[i] % p * i % p * i % p + phi[i - 1]) % p;
}
void clean() {
}
int solve() {
clean();
cin >> p >> nn;
init();
inv6 = ksm(6, p - 2), inv2 = ksm(2, p - 2); // 预处理逆元少一个log!
LL l = 1, ans = 0;
while (l <= nn) {
LL r = nn / (nn / l);
LL tmp2 = ((getphi(r) - getphi(l - 1)) % p + p) % p;
LL tmp3 = get3(nn / l) % p * get3(nn / l) % p;
ans = (ans + tmp2 % p * tmp3 % p) % p;
l = r + 1;
}
cout << ans;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
