BZOJ-2820: YY的GCD（莫比乌斯反演+分块）

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2820

这几天状态一直不太好，刷几道裸的数据结构都被虐成渣，于是乎就滚过来写数论题了，顺便发发题解攒RP，顺便GDKOI求轻虐。。。QaQ

思路（之前暴力枚举质数的我真是傻X）：

42166d224f4a20a401d7f88092529822730ed0a8.jpg.png

然后，我们就用前缀和来维护h(x),用筛法预处理h(x),u(x),用分块的方法处理[n/x][m/x],那么就可以做到O( t sqrt( n ) )的复杂度，可以AC此题啦~（u(x)表示莫比乌斯函数）

代码：

#include <cstdio>

#include <algorithm>
#include <cstring>
 
using namespace std ;
 
#define MAXN 10001000
#define MAXP 1000010
#define ll long long
#define Sum( l , r ) ( sum[ r ] - sum[ l - 1 ] )
#define MAXT 10010
 
bool f[ MAXN ] ;
ll u[ MAXN ] , h[ MAXN ] , p[ MAXP ] , pn , sum[ MAXN ] , maxn , tot , q[ MAXT ][ 2 ] ;
 
void Init(  ) {
    maxn = 0 ;
    scanf( "%lld" , &tot ) ;
    for ( int i = 0 ; i ++ < tot ; ) {
        scanf( "%lld%lld" , &q[ i ][ 0 ] , &q[ i ][ 1 ] ) ;
        maxn = max( maxn , max( q[ i ][ 0 ] , q[ i ][ 1 ] ) ) ;
    }
    for ( int i = 0 ; i <= maxn ; ++ i ) f[ i ] = true , u[ i ] = h[ i ] = 0 ;
    pn = 0 ;
    f[ 1 ] = f[ 0 ] = false , u[ 1 ] = 1 ;
    for ( int i = 1 ; i ++ < maxn ; ) if ( f[ i ] ) {
        p[ ++ pn ] = i , u[ i ] = - 1 ;
        for ( int j = i << 1 ; j <= maxn ; j += i ) {
            if ( ( j / i ) % i ) {
                u[ j ] = u[ j / i ] * ( - 1 ) ;
            } else {
                u[ j ] = 0 ;
            }
            f[ j ] = false ;
        }
    }
    for ( int i = 0 ; i ++ < maxn ; ) {
        for ( int j = 1 ; j <= pn && i * p[ j ] <= maxn ; ++ j ) {
            h[ i * p[ j ] ] += u[ i ] ;
        }
    }
    sum[ 0 ] = 0 ;
    for ( int i = 0 ; i ++ < maxn ; ) sum[ i ] = sum[ i - 1 ] + h[ i ] ;
}
 
ll query( int n , int m ) {
    ll ans = 0 ;
    for ( int i = 1 ; i <= min( n , m ) ; ) {
        int pos = min( n / ( n / i ) , m / ( m / i ) ) ;
        ans += Sum( i , pos ) * ( ll )( n / i ) * ( ll )( m / i ) ;
        i = pos + 1 ;
    }
    return ans ;
}
 
int main(  ) {
    Init(  ) ;
    for ( ll i = 0 ; i ++ < tot ; ) {
        printf( "%lld\n" , query( q[ i ][ 0 ] , q[ i ][ 1 ] ) ) ;
    }
    return 0 ;
}