@
peng-ym
\(\sum_{d|n} \mu(d) = [n = 1]\)
\(\sum_{d|n}\phi(d) = n\)
\(\phi(n) = \sum_{d|n} \mu(d)\frac{n}{d}\) ??\((容斥过程)\)
\(\sum_{d|gcd(i,j)} \mu(d) = [gcd(i,j) = 1]\;-C\)
\(F(n)=\sum_{d|n}f(d) => f(n)=\sum_{d|n}u(d)F(?\frac{n}{d}?)\;-B\)
\(F(n)=\sum_{n|d}f(d) => f(n)=\sum_{n|d}u(\frac{d}{n})F(d)\;-A\)
\(ans = \sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)\;\;\;n\leq m\leq1e7\)
\(ans = \sum_{d=1}^{n}d \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=d]=\sum_{d=1}^{n} d\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[gcd(i,j)=1]\)
法1：
\(f(d)=\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=d]\)并且\(F(n)=\sum_{n|d}f(d)\)
\(F(n)=\sum_{i=1}^{n}\sum_{j=1}^{m}[d|gcd(i,j)]=?\frac{n}{d}?\times ? \frac{m}{d}?\)
\(f(x)=\sum_{x|d}^{min(n,m)}u(\frac{d}{x})F(d)\)
\(f(1)=\sum_{d=1}^{min(n,m)}u(d)F(d)=\sum_{d=1}^{min(n,m)}u(d)?\frac{n}{d}?\times ? \frac{m}{d}?\)
\(ans = \sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d}}u(i)\frac{n}{d\times i}\frac{m}{d\times i}\)
法2：(无敌易理解)
\(\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)} u(d)\)
\(\sum_{d=1}^{n}u(d)\sum_{i=1}^{n}\sum_{j=1}^{m}[d|gcd(i,j)]=\sum_{d=1}^{n}u(d)?\frac{n}{d}??\frac{m}{d}?\)
\(ans = \sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d}}u(i)\frac{n}{d\times i}\frac{m}{d\times i}\)
这是一个神奇的Blog
AC_CODE：
传送门
\(ans=\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=prime]\;\;n\leq m\leq 1e7\)
\(ans=\sum_{d=1}^{n}\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}[gcd(i,j)=1]\)
\(ans=\sum_{d=1}^{n}\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}\sum_{k|gcd}\mu(k)\)
\(ans=\sum_{d=1}^{n}\sum_{k=1}^{\frac{n}{d}}\mu(k)\frac{n}{kd}\frac{m}{kd}\)
这样写会超时，因为多组数据，还得优化，就是交换求和顺序，令\(T=kd：\)
\(ans=\sum_{T=1}^{n}\frac{n}{T}\frac{m}{T}\sum_{d|T}\mu(\frac{T}{d})\)
预处理：\(\sum_{d|T}\mu(\frac{T}{d})\) 这个式子：枚举每个素数，给它的\(x\)倍数加上\(\mu(x)\)，然后前缀和。
AC_CODE：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MXN = 1e7+ 7;
const int mod = 998244353;
LL n, m;
int noprime[MXN], pp[MXN], pcnt;
int phi[MXN], mu[MXN];
LL pre_mu[MXN];
void init_prime() {
noprime[0] = noprime[1] = 1;
mu[1] = 1; phi[1] = 1;
for(int i = 2; i < MXN; ++i) {
if(!noprime[i]) pp[pcnt++] = i, phi[i] = i-1, mu[i] = -1;
for(int j = 0; j < pcnt && pp[j] * i < MXN; ++j) {
noprime[pp[j]*i] = 1;
//phi[pp[j]*i] = (pp[j]-1)*phi[i];
mu[pp[j]*i] = -mu[i];
if(i % pp[j] == 0) {
//phi[pp[j]*i] = pp[j]*phi[i];
mu[pp[j]*i] = 0;
break;
}
}
}
}
void init_ans() {
for(int i = 0; i < pcnt; ++i) {
for(int j = 1; j*pp[i] < MXN; ++j) {
pre_mu[j*pp[i]] += mu[j];
}
}
for(int i = 2; i < MXN; ++i) pre_mu[i] += pre_mu[i-1];
}
int main() {
init_prime();
init_ans();
int tim; scanf("%d", &tim);
while(tim --) {
scanf("%lld%lld", &n, &m);
if(n > m) swap(n, m);
LL ans = 0, tmp;
for(LL L = 1, R; L <= n; L = R + 1) {
R = min(n/(n/L),m/(m/L));
tmp = pre_mu[R]-pre_mu[L-1];
ans = (ans + tmp*(n/L)*(m/L));
}
printf("%lld\n", ans);
}
return 0;
}\(ans=\sum_{i=1}^{n}\sum_{j=1}^{n}\mu(gcd(i,j))\;\;n\leq1e11\)
\(ans = \sum_{d=1}^{n}\mu(d) \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=d]=\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}[gcd(i,j)=1]\)
\(F(n)=\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)=1],\;P(n)=\sum_{i=1}^{n}\phi(i)=\sum_{i=1}^{n}\sum_{j=1}^{i}[gcd(i,j)=1]\)
\(F(n)=P(n)\times2 -1\)
\(ans = \sum_{d=1}^{n}\mu(d)\times(P(\frac{n}{d})\times 2-1)\)
AC_CODE：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MXN = 1e7+ 7;
const LL mod = 998244353;
const LL inf = 1e18;
LL n, m, inv2;
int noprime[MXN], pp[MXN], pcnt;
int phi[MXN], mu[MXN];
LL pre_mu[MXN], pre_phi[MXN];
//unordered_map<LL, LL> mp1, mp2;
void init_prime() {
noprime[0] = noprime[1] = 1;
mu[1] = 1; phi[1] = 1;
for(int i = 2; i < MXN; ++i) {
if(!noprime[i]) pp[pcnt++] = i, phi[i] = i-1, mu[i] = -1;
for(int j = 0; j < pcnt && pp[j] * i < MXN; ++j) {
noprime[pp[j]*i] = 1;
phi[pp[j]*i] = (pp[j]-1)*phi[i];
mu[pp[j]*i] = -mu[i];
if(i % pp[j] == 0) {
phi[pp[j]*i] = pp[j]*phi[i];
mu[pp[j]*i] = 0;
break;
}
}
}
for(int i = 1; i < MXN; ++i) {
pre_mu[i] = pre_mu[i-1] + mu[i];
pre_phi[i] = (pre_phi[i-1] + phi[i])%mod;
}
}
struct Hash_map{
static const int mask=0x7fffff;
LL p[mask+1],q[mask+1];
void clear(){
memset(q,0,sizeof(q));
}
LL& operator [](LL k){
LL i;
for(i=k&mask;q[i]&&p[i]!=k;i=(i+1)&mask);
p[i]=k;
return q[i];
}
}mp1, mp2;
LL solve_mu(LL n) {
if(n < MXN) return pre_mu[n];
if(mp1[n] == inf) return 0;
if(mp1[n]) return mp1[n];
LL ans = 1;
for(LL L = 2, R; L <= n; L = R + 1) {
R = n/(n/L);
ans -= (R-L+1LL)%mod*solve_mu(n/L);
}
mp1[n] = ans;
if(mp1[n] == 0) mp1[n] = inf;
return ans;
}
LL solve_phi(LL n) {
if(n < MXN) return pre_phi[n];
if(mp2[n]) return mp2[n];
LL ans = n%mod*(n+1)%mod*inv2%mod;
for(LL L = 2, R; L <= n; L = R + 1) {
R = n/(n/L);
ans = (ans - (R-L+1LL)%mod*solve_phi(n/L)%mod)%mod;
}
ans = (ans + mod) % mod;
mp2[n] = ans;
return ans;
}
int main() {
inv2 = 499122177;
init_prime();
scanf("%lld", &n);
LL ans = 0;
for(LL L = 1, R; L <= n; L = R + 1) {
R = n/(n/L);
ans = (ans + (solve_mu(R)-solve_mu(L-1))%mod*(solve_phi(n/L)*2LL%mod-1LL)%mod+mod)%mod;
}
printf("%lld\n", (ans+mod)%mod);
return 0;
}原文：https://www.cnblogs.com/Cwolf9/p/10359344.html