程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [bzoj2301: [HAOI2011]Problem b] 求

[bzoj2301: [HAOI2011]Problem b] 求

編輯：C++入門知識

[bzoj2301: [HAOI2011]Problem b] 求

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;

inline int read(){
    int x = 0,f = 1; char ch = getchar();
    while(ch < '0'||ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >= '0'&&ch <= '9'){x = x * 10 + ch -'0';ch = getchar();}
    return x*f;
}

//////////////////////////////////////////////////////////////////

/*
算法：容斥原理 + 分塊
題目：
  對於給出的n個詢問，每次求有多少個數對(x,y)，滿足a≤x≤b，c≤y≤d，
  且gcd(x,y) = k，gcd(x,y)函數為x和y的最大公約數。
  
  1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000

*/

const int MAXN = 50000 + 10;
int tot;
LL mu[MAXN+1],sum[MAXN+1],pri[MAXN+1];
bool mark[MAXN];

void get(){
   mu[1] = 1;
   for(int i = 2;i <= MAXN;++i){
      if(!mark[i])pri[tot++] = i,mu[i] = -1;
      for(int j = 0;j < tot&&i*pri[j] <= MAXN;++j){
        mark[i*pri[j]] = 1;
        if(i % pri[j]==0){mu[i*pri[j]] = 0; break;}
        else mu[i*pri[j]] = -mu[i];
      }
   }

   for(int i = 1;i <= MAXN;++i) //預處理前綴
    sum[i] = sum[i-1] + mu[i];
}

int cal(int n,int m){
    if(n > m) swap(n,m);
    LL ans = 0,pos;
    for(LL i = 1;i <= n;i = pos + 1){
        pos = min(n/(n/i),m/(m/i));       //分塊
        ans += (sum[pos] - sum[i-1]) * (n/i) * (m/i);
    }
    return ans;
}

int main()
{
    get();
    int T = read();
    while(T--){
        int a = read(),b = read(),c = read(),d = read(),k = read();
        LL ans = cal(b/k,d/k);
        ans -= cal((a-1)/k,d/k);
        ans -= cal(b/k,(c-1)/k);
        ans += cal((a-1)/k,(c-1)/k);
        printf("%lld\n",ans);
    }
    return 0;
}