题解 | 算法竞赛进阶指南 Zap

思路

题意是求 $\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]$
莫比乌斯反演最重要的当然就是推柿子.假设 $n\le m$ ,不满足的话swap一下就OK了

$\begin{align} \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]&=\sum_{i=1}^{\lfloor n/d \rfloor}\sum_{j=1}^{\lfloor m/d \rfloor}[\gcd(i,j)=1]\\ &=\sum_{k=1}^{\lfloor n/d \rfloor}\mu(k)\times\lfloor n/(dk) \rfloor \times \lfloor m/(dk) \rfloor \end{align}$

这就是一个用数论分块可以解决的东西.只要预处理一下 $\mu$ 前缀和就OK了.
数论分块一次的复杂度为 $O(\log N)$ ,因此总复杂度为 $O(Q\log N)$ .
因为不是很卡常数所以没有优化除法....
至于如何优化除法可以参考https://www.luogu.org/problemnew/solution/SP26045

代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 50000

int T;
int mu[MAXN + 5], p[MAXN + 5], tot;
bool v[MAXN + 5];

int Work( int N, int M ){ int ans(0); if ( N > M ) swap( N, M );
    for ( int i = 1, j; i <= N; i = j + 1 ){
        j = min( N / ( N / i ), M / ( M / i ) );
        ans += ( N / i ) * ( M / i ) * ( mu[j] - mu[i - 1] );
    } return ans;
}

int main(){
    scanf( "%d", &T ); mu[1] = 1;
    for ( int i = 2; i <= MAXN; ++i ){
        if ( !v[i] ) p[++tot] = i, mu[i] = -1;
        for ( int j = 1; j <= tot && i * p[j] <= MAXN; ++j ){
            v[i * p[j]] = 1; mu[i * p[j]] = i % p[j] ? -mu[i] : 0;
            if ( i % p[j] == 0 ) break;
        }
    }
    for ( int i = 1; i <= MAXN; ++i ) mu[i] += mu[i - 1];
    while( T-- ){
        int a, b, d;
        scanf( "%d%d%d", &a, &b, &d ); a /= d; b /= d;
        printf( "%d\n", Work( a, b ) );
    }
    return 0;
}