https://www.luogu.com.cn/problem/P3312
就是要求
∑
i
=
1
n
∑
j
=
1
m
σ
(
g
c
d
(
i
,
j
)
)
\large \sum\limits_{i=1}^n\sum\limits_{j=1}^m\sigma(gcd(i,j))
i=1∑nj=1∑mσ(gcd(i,j))
按照套路开始推式子
∑
i
=
1
n
∑
j
=
1
m
σ
(
g
c
d
(
i
,
j
)
)
\large \sum\limits_{i=1}^n\sum\limits_{j=1}^m\sigma(gcd(i,j))
i=1∑nj=1∑mσ(gcd(i,j))
∑
d
=
1
σ
(
d
)
∑
i
=
1
n
/
d
∑
j
=
1
m
/
d
[
g
c
d
(
i
,
j
)
=
=
1
]
\large \sum\limits_{d=1}\sigma(d)\sum\limits_{i=1}^{n/d}\sum\limits_{j=1}^{m/d}[gcd(i,j)==1]
d=1∑σ(d)i=1∑n/dj=1∑m/d[gcd(i,j)==1]
把gcd换掉
∑
d
=
1
σ
(
d
)
∑
i
=
1
n
/
d
∑
j
=
1
m
/
d
∑
k
∣
i
,
k
∣
j
μ
(
k
)
\large \sum\limits_{d=1}\sigma(d)\sum\limits_{i=1}^{n/d}\sum\limits_{j=1}^{m/d}\sum\limits_{k|i,k|j}\mu(k)
d=1∑σ(d)i=1∑n/dj=1∑m/dk∣i,k∣j∑μ(k)
把
k
k
k提到前面
∑
d
=
1
σ
(
d
)
∑
k
=
1
n
/
d
μ
(
k
)
∑
i
=
1
n
/
k
d
∑
j
=
1
m
/
k
d
\large \sum\limits_{d=1}\sigma(d)\sum\limits_{k=1}^{n/d}\mu(k)\sum\limits_{i=1}^{n/kd}\sum\limits_{j=1}^{m/kd}
d=1∑σ(d)k=1∑n/dμ(k)i=1∑n/kdj=1∑m/kd
∑
d
=
1
σ
(
d
)
∑
k
=
1
n
/
d
μ
(
k
)
n
k
d
m
k
d
\large \sum\limits_{d=1}\sigma(d)\sum\limits_{k=1}^{n/d}\mu(k)\frac{n}{kd}\frac{m}{kd}
d=1∑σ(d)k=1∑n/dμ(k)kdnkdm
设 T = k d 设T=kd 设T=kd
∑ T = 1 ( n T ) ( m T ) ∑ k ∣ T μ ( k ) σ ( T k ) \large \sum\limits_{T=1}(\frac{n}{T})(\frac{m}{T})\sum\limits_{k|T}\mu(k)\sigma(\frac{T}{k}) T=1∑(Tn)(Tm)k∣T∑μ(k)σ(kT)
后面那个东西拿个树状数组维护一下就行了
code:
#include<bits/stdc++.h>
#define int long long
#define N 200005
#define lowbit(x) (x & (-x))
using namespace std;
const int lim = 100050;
const int mod = 2147483648;
struct A {
int x, y, z, id;
} q[N], a[N];
int cmp(A x, A y) {
return x.z < y.z;
}
int mu[N], vis[N], prime[N], sz, d[N];
void init() {
mu[1] = 1;
for(int i = 2; i <= lim; i ++) {
if(!vis[i]) {
prime[++ sz] = i;
mu[i] = mod - 1;
}
for(int j = 1; j <= sz && prime[j] * i < N; j ++) {
vis[prime[j] * i] = 1;
if(i % prime[j] == 0) {
mu[i * prime[j]] = 0;
break;
}
mu[i * prime[j]] = (mod - mu[i]) % mod;
}
}
for(int i = 1; i <= lim; i ++)
for(int j = i; j <= lim; j += i)
d[j] += i, d[j] %= mod;
for(int i = 1; i <= lim; i ++)
a[i].id = i, a[i].z = d[i];
sort(a + 1, a + 1 + lim, cmp);
}
int tree[N];
void update(int x, int y) {
for(; x < N; x += lowbit(x)) tree[x] += y;
}
int query(int x) {
int ret = 0;
for(; x; x -= lowbit(x)) ret += tree[x];
return ret;
}
void add(int x) {
for(int i = x; i <= lim; i += x) update(i, 1ll * d[x] * mu[i / x] % mod);
}
int calc(int n, int m) {
if(n > m) swap(n, m);
int ans = 0;
for(int l = 1, r = 0; l <= n; l = r + 1) {
r = min(n / (n / l), m / (m / l));
ans += 1ll * (n / l) * (m / l) % mod * (query(r) - query(l - 1) + mod) % mod;
ans = (ans + mod) % mod;
// printf("%lld %lld %lld %lld\n", ans, l, r, (query(r) - query(l - 1) + mod) % mod);
}
return ans % mod;
}
int ans[N], t;
signed main() {
init();
// for(int i = 1; i <= 20; i ++) printf("%lld ", a[i].id); printf("\n");
scanf("%lld", &t);
for(int i = 1; i <= t; i ++) scanf("%lld%lld%lld", &q[i].x, &q[i].y, &q[i].z), q[i].id = i;
sort(q + 1, q + 1 + t, cmp);
for(int i = 1, j = 1; i <= t; i ++) {
while(a[j].z <= q[i].z && j <= lim) add(a[j ++].id);
ans[q[i].id] = calc(q[i].x, q[i].y);
}
for(int i = 1; i <= t; i ++) printf("%lld\n", ans[i]);
return 0;
}
做题要想清楚后再做，不要看代码，不要急着看题解
知识点要掌握熟悉