題目：http://www.lydsy.com/JudgeOnline/problem.php?id=2820
這幾天狀態(tài)一直不太好具练，刷幾道裸的數(shù)據(jù)結(jié)構(gòu)都被虐成渣豹芯，于是乎就滾過來寫數(shù)論題了，順便發(fā)發(fā)題解攢RP心肪，順便GDKOI求輕虐费就。润文。禾进。QaQ
思路（之前暴力枚舉質(zhì)數(shù)的我真是傻X）：
42166d224f4a20a401d7f88092529822730ed0a8.jpg.png
然后豁跑，我們就用前綴和來維護(hù)h(x),用篩法預(yù)處理h(x),u(x),用分塊的方法處理[n/x][m/x],那么就可以做到O( t sqrt( n ) )的復(fù)雜度，可以AC此題啦~（u(x)表示莫比烏斯函數(shù)）
代碼：
#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 ;
}
