数学题¶
题意¶
给定 n,m，求 \sum\limits_{i=1}^n\sum\limits_{j=1}^m\left\lfloor\dfrac{i}{j}\right\rfloor\gcd(i,j)。
解析¶
这个 GCD 显然要反演掉。反演最大公约数常用的方法有欧拉反演和莫比乌斯反演，这里我们选用欧拉反演。
则原式转化为
\sum_{d=1}^m\varphi(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor}\left\lfloor\dfrac{i}{j}\right\rfloor
设 f(x,y)=\sum_{i=1}^x\sum_{j=1}^y\left\lfloor\dfrac{i}{j}\right\rfloor。若我们能 O(y) 求出 f(x,y)，那么就可以以调和级数复杂度求出答案了。
\begin{aligned}
f(x,y)&=\sum_{i=1}^x\sum_{j=1}^y\left\lfloor\dfrac{i}{j}\right\rfloor\\
&=\sum_{k=1}^x\sum_{i=1}^x\sum_{j=1}^y\left[\left\lfloor\dfrac{i}{j}\right\rfloor\ge k\right]\\
&=\sum_{k=1}^x\sum_{i=1}^x\sum_{j=1}^y[i\ge jk]\\
&=\sum_{i=1}^y\sum_{k=1}^x\max(x-ik+1,0)\\
&=\sum_{i=1}^y\sum_{k=1}^{\lfloor\frac{x+1}{i}\rfloor}(x-ik+1)
\end{aligned}
里面是个等差数列求和。于是我们以 O(m\log m) 的复杂度解决了这道题。
#include <bits/stdc++.h>
typedef unsigned long long int ull;
const int maxn = 1e7 + 19;
ull f(int x, int y){
ull res = 0ull;
for(int i = 1; i <= y; ++i){
int mx = (x + 1) / i;
res += (((ull)x - i + 1 + x - (ull)mx * i + 1) * mx) >> 1;
}
return res;
}
int n, m;
int prime[maxn], cnt, phi[maxn];
bool vist[maxn];
int main(){
std::scanf("%d%d", &n, &m);
phi[1] = 1;
for(int i = 2; i <= m; ++i){
if(!vist[i]) prime[++cnt] = i, phi[i] = i - 1;
for(int j = 1; j <= cnt && i * prime[j] <= m; ++j){
vist[i * prime[j]] = true;
if(i % prime[j]) phi[i * prime[j]] = phi[i] * (prime[j] - 1);
else{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
}
}
ull ans = 0ull;
for(int i = 1; i <= m; ++i)
ans += (ull)phi[i] * f(n / i, m / i);
ans &= (1ull << 60) - 1;
std::printf("%llu\n", ans);
return 0;
}