BZOJ 2005: [Noi2010]能量采集 [莫比乌斯反演]

题意：\((0,0)\)到\((x,y),\ x \le n, y \le m\)连线上的整点数\(*2-1\)的和

---

\((0,0)\)到\((a,b)\)的整点数就是\(gcd(a,b)\)

因为...直线上的整点...扩展欧几里得...每\(\frac{a}{d}\)有一个解，到\(a\)你说有几个解...



套路推♂倒见学习笔记

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1e5+5;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
    return x*f;
}

int n, m, k;
int notp[N], p[N];ll phi[N];
void sieve(int n) {
    phi[1] = 1;
    for(int i=2; i<=n; i++) {
        if(!notp[i]) p[++p[0]] = i, phi[i] = i-1;
        for(int j=1; j<=p[0] && i*p[j]<=n; j++) {
            notp[i*p[j]] = 1;
            if(i%p[j] == 0) {phi[i*p[j]] = phi[i]*p[j]; break;}
            phi[i*p[j]] = phi[i]*(p[j]-1);
        }
    }
    for(int i=1; i<=n; i++) phi[i] += phi[i-1];
}
ll cal(int n, int m) {
    ll ans=0; int r;
    for(int i=1; i<=n; i=r+1) {
        r = min(n/(n/i), m/(m/i));
        ans += (phi[r] - phi[i-1]) * (n/i) * (m/i);
    }
    return ans;
}
int main() {
    //freopen("in","r",stdin);
    n=read(); m=read();
    if(n>m) swap(n, m);
    sieve(n);
    printf("%lld", 2*cal(n, m) - (ll)n*m);
}