题目：
http://www.lydsy.com/JudgeOnline/problem.php?id=1257
http://www.lydsy.com/JudgeOnline/problem.php?id=2301
http://www.lydsy.com/JudgeOnline/problem.php?id=1101
数论一向就是本蒟蒻最渣渣的内容，无奈去啃了一下：
1257: [CQOI2007]余数之和sum:
由于a%b=a-(a/b)*b,那么对于a/b进行分段统计即可，复杂度sqrt(n)
Code:
#include <iostream>
using namespace std ;
#define ll long long
ll n , k , ans = 0 ;
int main( ) {
cin >> n >> k ;
for ( ll i = 1 ; i <= n ; ) {
if ( i > k ) {
ans += ( n - i + 1 ) * k ; break ;
}
ll pos = min( k / ( k / i ) , n ) ;
ans += ( k * ( pos - i + 1 ) - ( k / i ) * ( pos - i + 1 ) * ( i + pos ) / 2 ) ;
i = pos + 1 ;
}
cout << ans << endl ;
return 0 ;
}
1101: [POI2007]Zap：
要求1<=x<=a,1<=y<=b,gcd(x,y)=c的数对数目，那么就相当于求，gcd(x/c,y/c)=1,1<=x<=a/c,1<=y<=b/c的数目，然后再用神奇的莫比乌斯反演可以得到答案是，sigma u(d)(a/(cd))(b/(cd)),然后就像上一题一样，对a/(cd)分段统计即可，总复杂度O(n^1.5)
Code:
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
#define MAX 50100
#define Sum( l , r ) ( sum[ r ] - sum[ l - 1 ] )
bool f[ MAX ] ;
int u[ MAX ] , sum[ MAX ] , maxd = 0 , n , A[ MAX ] , B[ MAX ] , C[ MAX ] ;
void Init( ) {
scanf( "%d" , &n ) ;
for ( int i = 0 ; i ++ < n ; ) {
scanf( "%d%d%d" , &A[ i ] , &B[ i ] , &C[ i ] ) ;
maxd = max( maxd , max( A[ i ] , B[ i ] ) / C[ i ] ) ;
}
memset( f , true , sizeof( f ) ) ;
f[ 0 ] = f[ 1 ] = false ;
memset( u , 0 , sizeof( u ) ) ; u[ 1 ] = 1 ;
for ( int i = 1 ; i ++ < maxd ; ) if ( f[ i ] ) {
u[ i ] = - 1 ;
for ( int j = i << 1 ; j <= maxd ; j += i ) {
if ( ! ( ( j / i ) % i ) ) u[ j ] = 0 ;
else u[ j ] = u[ j / i ] * - 1 ;
f[ j ] = false ;
}
}
sum[ 0 ] = 0 ;
for ( int i = 1 ; i <= maxd ; ++ i ) sum[ i ] = sum[ i - 1 ] + u[ i ] ;
}
void Solve( ) {
for ( int j = 0 ; j ++ < n ; ) {
int a , b , c , ans = 0 ;
a = A[ j ] , b = B[ j ] , c = C[ j ] ;
a /= c , b /= c ;
if ( a > b ) swap( a , b ) ;
for ( int i = 1 ; i <= a ; ) {
int pos = min( a / ( a / i ) , b / ( b / i ) ) ;
ans += Sum( i , pos ) * ( a / i ) * ( b / i ) ;
i = pos + 1 ;
}
printf( "%d\n" , ans ) ;
}
}
int main( ) {
Init( ) ;
Solve( ) ;
return 0 ;
}
2301: [HAOI2011]Problem b：
上一道题的略略加强版，设f(a,b)为gcd(x,y)=1,1<=x<=a,1<=y<=b的数目，那么gcd(x,y)=1,a<=x<=b,c<=y<=d的数目用容斥定理弄一下就成了f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1)，然后用上题的方法就可以统计出来了。
Code:
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
#define Sum( l , r ) ( sum[ r ] - sum[ l - 1 ] )
#define MAX 51000
int n , A[ MAX ] , B[ MAX ] , C[ MAX ] , D[ MAX ] , K[ MAX ] ;
int u[ MAX ] , sum[ MAX ] , maxd = 0 ;
bool f[ MAX ] ;
void Init( ) {
scanf( "%d" , &n ) ;
for ( int i = 0 ; i ++ < n ; ) {
scanf( "%d%d%d%d%d" , A + i , B + i , C + i , D + i , K + i ) ;
maxd = max( maxd , max( B[ i ] , D[ i ] ) / K[ i ] ) ;
}
memset( f , true , sizeof( f ) ) ;
memset( u , 0 , sizeof( u ) ) ;
memset( sum , 0 , sizeof( sum ) ) ;
f[ 0 ] = f[ 1 ] = false , u[ 1 ] = 1 ;
for ( int i = 1 ; i ++ < maxd ; ) if ( f[ i ] ) {
u[ i ] = - 1 ;
for ( int j = i << 1 ; j <= maxd ; j += i ) {
if ( ! ( ( j / i ) % i ) ) u[ j ] = 0 ; else u[ j ] = u[ j / i ] * - 1 ;
f[ j ] = false ;
}
}
for ( int i = 0 ; i ++ < maxd ; ) sum[ i ] = sum[ i - 1 ] + u[ i ] ;
}
int query( int a , int b ) {
int ans = 0 ;
for ( int i = 1 ; i <= min( a , b ) ; ) {
int pos = min( a / ( a / i ) , b / ( b / i ) ) ;
ans += Sum( i , pos ) * ( a / i ) * ( b / i ) ;
i = pos + 1 ;
}
return ans ;
}
void Solve( ) {
for ( int i = 0 ; i ++ < n ; ) {
A[ i ] -- , C[ i ] -- ;
A[ i ] /= K[ i ] , B[ i ] /= K[ i ] , C[ i ] /= K[ i ] , D[ i ] /= K[ i ] ;
printf( "%d\n" , query( B[ i ] , D[ i ] ) - query( A[ i ] , D[ i ] ) - query( B[ i ] , C[ i ] ) + query( A[ i ] , C[ i ] ) ) ;
}
}
int main( ) {
Init( ) ;
Solve( ) ;
return 0 ;
}
