P1447 [NOI2010]能量采集 [容斥 / "欧拉反演"]

$能量采集$能量采集

$Description$Description
求解 $2\ast \sum _{i=1}^N\sum _{j=1}^{M}gcd(i,j)-N\ast M$2∗i=1∑N​j=1∑M​gcd(i,j)−N∗M

做这道题前可以先看看 仪仗队 .

$正解部分$正解部分
首先说一下为什么求解的是上方的式子,
对一个点 $(x,y)$(x,y), 遮拦这个点的个数为 $gcd(x,y)-1$gcd(x,y)−1, 又因为一个点的贡献为 $2\left(gcd\right(x,y)-1)+1$2(gcd(x,y)−1)+1, 所以可以得到上式 .

重点为下方这个式子:
$\sum _{i=1}^N\sum _{j=1}^{M}gcd(i,j)$i=1∑N​j=1∑M​gcd(i,j)

解法 $1$1:

容斥原理

考虑枚举 $d$d, 统计有多少 $(i,j)$(i,j) 满足 $gcd(i,j)=d$gcd(i,j)=d,
以 $d$d 为约数的点对数为 $\lfloor \frac{N}{d}\rfloor \lfloor \frac{M}{d}\rfloor$⌊dN​⌋⌊dM​⌋ ,
只需将 $d$d 不是最小公倍数的点对数减去就行了, 具体 容斥 过程见代码 .
时间复杂度 $O\left(NlogN\right)$O(NlogN)

#include<cstdio>
#include<algorithm>
#define reg register
typedef long long ll;

const int maxn = 100005;

int N;
int M;

ll Ans;
ll cnt[maxn];

int main(){
        scanf("%d%d", &N, &M);
        for(reg int d = std::min(N, M); d >= 1; d --){
                cnt[d] = (1ll*M/d) * 1ll*(N/d);
                for(reg int j = 2; j*d <= std::min(N, M); j ++) cnt[d] -= cnt[j*d];
                Ans += (d*2 - 1) * cnt[d];
        }
        printf("%lld\n", Ans);
        return 0;
}

解法 $2$2:

欧拉反演

存在这个等式 $\downarrow$↓
$\sum _{d\mid N}\phi \left(d\right)=N$d∣N∑​φ(d)=N

如果不懂请点击 这里

将 $N$N 换为 $gcd(i,j)$gcd(i,j), 原式变为 $\downarrow$↓
$\sum _{i=1}^N\sum _{j=1}^M\sum _{d\mid gcd(i,j)}\phi \left(d\right)$i=1∑N​j=1∑M​d∣gcd(i,j)∑​φ(d)

$\sum _{d=1}^N\phi \left(d\right)\lfloor \frac{N}{d}\rfloor \lfloor \frac{M}{d}\rfloor$d=1∑N​φ(d)⌊dN​⌋⌊dM​⌋

代码略 .