2301: [HAOI2011]Problem b ( 分块+莫比乌斯反演+容斥）

2301: [HAOI2011]Problem b

Time Limit: 50 Sec Memory Limit: 256 MB
Submit: 6015 Solved: 2741
[Submit][Status][Discuss]

Description

对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。

Input

第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k

Output

共n行，每行一个整数表示满足要求的数对(x,y)的个数

Sample Input

2 5 1 5 1

1 5 1 5 2

Sample Output

HINT

100%的数据满足：1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000

/*

* @Author: LyuC

* @Date:   2017-10-08 16:54:59

* @Last Modified by:   LyuC

* @Last Modified time: 2017-10-08 21:06:44

*/

/*

 直接处理会超时，对于6/6=1 6/5=1 6/4=1这样的实际和已合并同类项一次

    计算出来，能节约不少时间

*/

#include <bits/stdc++.h>

#define LL long long

#define MAXN 50005

using namespace std;

int t;

int a, b, c, d, k;

int sum [ MAXN ];

bool check[MAXN];

int mu[MAXN];

int prime[MAXN];

void mobi(){

     memset(check,false,sizeof check);

     mu[]=;

     int tol=;

     for(int i=;i<MAXN;i++){

         if(!check[i]){

             prime[tol++]=i;

             mu[i]=-;

         }

         for(int j=;j<tol;j++){

             if(i*prime[j]>MAXN) break;

             check[i*prime[j]]=true;

             if(i%prime[j]==){

                 mu[i*prime[j]]=;

                 break;

             }else{

                 mu[i*prime[j]]=-mu[i];

             }

         }

     }

}

inline int Count (int a, int b) {

    int s=;

    if (a > b) {

        swap (a, b);

    }

    for (int i = , last = ; i <= a; i = last + ) {

        last = min( a / (a / i), b / (b / i) );

        s += (sum [ last ] - sum [ i -  ]) * (a / i) * (b / i);

    }

    return s;

}

inline void init () {

    sum [  ] = ;

    for (int i = ;i < MAXN; i ++) {

        sum [ i ] = sum[ i -  ] + mu [ i ];

    }

}

int main () {

    // freopen ("in.txt", "r", stdin);

    mobi ();

    init ();

    scanf ("%d", &t);

    while (t -- ) {

        scanf ("%d%d%d%d%d", &a, &b, &c, &d, &k);

        int res = Count ( b / k, d / k ) - Count ( ( a -  ) / k, d / k ) - Count ( b / k, (c - ) / k ) + Count ( ( a -  ) / k, ( c - ) / k );

        printf ( "%d\n", res );

    }

    return ;

}

巴特西