BZOJ 2005: [NOI2010]能量采集 – [欧拉函数]

题目传送门(BZOJ)
>原文链接<

题解 :

对于一个坐标(x, y), 我们要知道k = \gcd(x, y)-1

证明 :

设\gcd(x, y) = t, 则x=at, y = bt,

所有在这条直线上的整数点坐标为(a, b), (2a, 2b), (3a, 3b)\cdots(ta, tb)共t个,

又因为(x, y)不算在内, 所以是t-1即\gcd(x, y)-1

则(x, y)损耗就是2\times \gcd(x, y)-1

所以原题就变成了求这个式子 :

\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}(\gcd(i, j)\times 2-1)

= 2\times \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\gcd(i,j)-n\times m

需要处理的就只有\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\gcd(i,j)

由\sum\limits_{d|n}\varphi(d) = n

\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{d|\gcd(i, j)}\varphi(d)

枚举d

\sum\limits_{d=1}^{n}\sum\limits_{i=1}^n\sum\limits_{j=1}^m[d|i,d|j]\varphi(d)

在n范围内, d|i的数量是\lfloor\frac{n}{d}\rfloor

故枚举总量不变, 原式可化为 :

\sum\limits_{d=1}^{n}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\varphi(d)

所以直接\sqrt n+\sqrt m分块求和, 线筛预处理S_\varphi即可

代码 :

#include
#include
#include
using namespace std;
#define ll long long
const int N = 1e5+5;
bool np[N];
ll n, m, ans;
ll phi[N], pr[N];
inline void init() {
    phi[1] = 1;
    for(int i = 2; i <= n; i ++ ) {
        if(!np[i]) {
            pr[++*pr] = i;
            phi[i] = i-1;
        }
        for(int j = 1; j <= *pr&&i*pr[j] <= n; j ++ ) {
            np[i*pr[j]] = 1;
            if(i%pr[j] == 0) {
                phi[i*pr[j]] = phi[i]*pr[j];
                break;
            }
            else phi[i*pr[j]] = phi[i]*(pr[j]-1);
        }
        phi[i] += phi[i-1];
    }
}
int main() {
    scanf("%lld%lld",&n,&m); if(n>m) swap(n,m);
    init();
    for(ll i = 1,lst; i <= n; i = lst+1) {
        lst = min(n/(n/i),m/(m/i));
        ans += (ll)(phi[lst]-phi[i-1])*(n/i)*(m/i);
    }
    printf("%lld\n",ans*2-n*m);
}