资料 http://wenku.baidu.com/view/542961fdba0d4a7302763ad5.html
还有一些就看百度百科或者其他人的blog。并不是很懂
是二维的，这个是三维版本。二维的可以用欧拉函数做。三维用莫比乌斯反演做，具体解释看 。我并没有很懂，感觉莫比乌斯反演好牛逼啊
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 8 using namespace std; 9 10 #define LL long long11 #define eps 1e-812 #define lson l, m, rt<<113 #define rson m+1, r, rt<<1|114 #define mnx 100010015 16 bool check[mnx];17 int mu[mnx], tot, prime[mnx];18 void init(){19 mu[1] = 1;20 for( int i = 2; i < mnx; ++i ){21 if( !check[i] )22 prime[tot++] = i, mu[i] = -1;23 for( int j = 0; i * prime[j] < mnx &&j < tot; ++j ){24 check[i*prime[j]] = 1;25 if( i % prime[j] == 0 ){26 mu[i*prime[j]] = 0;27 break;28 }29 else mu[i*prime[j]] = -mu[i];30 }31 }32 }33 int main(){34 int cas;35 scanf( "%d", &cas );36 init();37 while( cas-- ){38 int n;39 scanf( "%d", &n );40 LL ans = 0;41 for( int i = 1; i <= n; ++i )42 ans += (LL)mu[i] * (n/i) * (n/i) * (n/i+3); //(+3是指x-y, x-z, y-z三个平面)43 printf( "%lld\n", ans + 3 );44 }45 return 0;46 }
做了上题，这题就没什么难度了。已经用容斥搞过了，不过容斥比莫比乌斯反演慢很多。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 8 using namespace std; 9 10 #define LL long long11 #define eps 1e-812 #define lson l, m, rt<<113 #define rson m+1, r, rt<<1|114 #define mnx 10010015 16 bool check[mnx];17 int mu[mnx], tot, prime[mnx];18 void init(){19 mu[1] = 1;20 for( int i = 2; i < mnx; ++i ){21 if( !check[i] )22 prime[tot++] = i, mu[i] = -1;23 for( int j = 0; i * prime[j] < mnx &&j < tot; ++j ){24 check[i*prime[j]] = 1;25 if( i % prime[j] == 0 ){26 mu[i*prime[j]] = 0;27 break;28 }29 else mu[i*prime[j]] = -mu[i];30 }31 }32 }33 int main(){34 int cas, kk = 1;35 scanf( "%d", &cas );36 init();37 while( cas-- ){38 LL n, m, nn, mm, k;39 scanf( "%I64d%I64d%I64d%I64d%I64d", &nn, &n, &mm, &m, &k );40 if( k == 0 ){41 printf( "Case %d: 0\n", kk++ ); continue ;42 }43 n /= k, m /= k;44 if( n > m ) swap( n, m );45 LL ans = 0, ans1 = 0;46 for( int i = 1; i <= n; ++i )47 ans += (LL)mu[i] * (n/i) * (m/i);48 for( int i = 1; i <= n; ++i )49 ans1 += (LL)mu[i] * (n/i) * (n/i);50 printf( "Case %d: %I64d\n", kk++, ans - ans1/2 );51 }52 return 0;53 }
中文题。对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k。
上题已经做了1 <= x <= b，1 <= y <= d，且gcd( x, y ) = k的。因此，对a <= x <= b, c <= y <= d，可以用容斥搞。ans = calc( b, d ) - calc( a-1, d ) - calc( b, c-1 ) + calc( a-1, c-1 );但是题目有5w组case，每组case都是O(n)的复杂度，会tle，因此还需要再优化。用分块的方法，因为对于一段区间，( L / i ), ( R / i )的值可能是一样的。所以我们先预处理莫比乌斯函数的前缀和，然后对于i，令j = min( L/(L/i), R/(R/i) )，区间 [ i，j ]的商都是一样的，所以ret += (s[j] - s[i-1] ) * (L/i) * (R/i);这样处理后复杂度的O(sqrt(n))，5w组case就可以过了
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 9 using namespace std;10 11 #define LL long long12 #define eps 1e-813 #define pb push_back14 #define pf push_front15 #define lson l, m, rt<<116 #define rson m+1, r, rt<<1|117 #define mnx 5100018 19 bool check[mnx];20 int mu[mnx], tot, prime[mnx], s[mnx];21 void init(){22 mu[1] = 1;23 for( int i = 2; i < mnx; ++i ){24 if( !check[i] )25 prime[tot++] = i, mu[i] = -1;26 for( int j = 0; j < tot && i * prime[j] < mnx; ++j ){27 check[i*prime[j]] = 1;28 if( i % prime[j] == 0 ){29 mu[i*prime[j]] = 0;30 break;31 }32 else mu[i*prime[j]] = -mu[i];33 }34 }35 for( int i = 1; i < mnx; ++i )36 s[i] = s[i-1] + mu[i];37 }38 int a, b, c, d, k;39 LL calc( int L, int R ){40 L /= k, R /= k;41 LL ret = 0;42 if( L == 0 || R == 0 ) return 0;43 if( L > R ) swap( L, R );44 for( int i = 1, j; i <= L; i = j+1 ){45 j = min( L/(L/i), R/(R/i) );46 ret += (LL)( s[j] - s[i-1] ) * ( L/i ) * ( R/i );47 }48 return ret;49 }50 int main(){51 init();52 int cas;53 scanf( "%d", &cas );54 while( cas-- ){55 scanf( "%d%d%d%d%d", &a, &b, &c, &d, &k );56 LL ans = calc( b, d ) - calc( a-1, d ) - calc( b, c-1 ) + calc( a-1, c-1 );57 printf( "%lld\n", ans );58 }59 return 0;60 }