[n/x] = y
xx = [n/y]
则xx是最大的被除数，使得商向下取证不变。
1 /************************************************************** 2 Problem: 2301 3 User: idy002 4 Language: C++ 5 Result: Accepted 6 Time:10136 ms 7 Memory:1880 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <iostream> 12 using namespace std; 13 14 int a, b, c, d, k; 15 int prm[6000], isnot[50010], mu[50010], smu[50010], ptot; 16 17 18 void init( int n ) { 19 mu[1] = 1; 20 for( int i=2; i<=n; i++ ) { 21 if( !isnot[i] ) { 22 prm[++ptot] = i; 23 mu[i] = -1; 24 } 25 for( int j=1; j<=ptot && i*prm[j]<=n; j++ ) { 26 isnot[i*prm[j]] = true; 27 if( i%prm[j]==0 ) { 28 mu[i*prm[j]] = 0; 29 break; 30 } 31 mu[i*prm[j]] = -mu[i]; 32 } 33 } 34 for( int i=1; i<=n; i++ ) 35 smu[i] = smu[i-1]+mu[i]; 36 } 37 int calc( int n, int m ) { 38 n /= k; 39 m /= k; 40 if( n>m ) swap(n,m); 41 int rt = 0; 42 for( int i=1; i<=n; i++ ) { 43 int ii = min( m/(m/i), n/(n/i) ); 44 rt += (smu[ii]-smu[i-1])*(m/i)*(n/i); 45 i = ii; 46 } 47 return rt; 48 } 49 int main() { 50 int T; 51 scanf( "%d", &T ); 52 init( 50000 ); 53 while( T-- ) { 54 scanf( "%d%d%d%d%d", &a, &b, &c, &d, &k ); 55 printf( "%d ", calc(b,d)-calc(a-1,d)-calc(b,c-1)+calc(a-1,c-1) ); 56 } 57 }