BZOJ 2301: [HAOI2011]Problem b （莫比乌斯反演）-白红宇

BZOJ 2301: [HAOI2011]Problem b （莫比乌斯反演）

阅读量：6312 次

发布时间：2019-06-22

本文共 1878 字，大约阅读时间需要 6 分钟。

2301: [HAOI2011]Problem b

Time Limit: 50 Sec Memory Limit: 256 MB

Submit: 436 Solved: 187

[ ][ ]

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

Source

[ ][ ]

Back

思路可以参考下面的链接：

分段优化。

/* ***********************************************Author        :kuangbinCreated Time  :2013/8/21 20:19:04File Name     :F:\2013ACM练习\专题学习\数学\莫比乌斯反演\BZOJ2301.cpp************************************************ */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #include 
                
                 using namespace std;const int MAXN = 100000;bool check[MAXN+10];int prime[MAXN+10];int mu[MAXN+10];void Moblus(){ memset(check,false,sizeof(check)); mu[1] = 1; int tot = 0; for(int i = 2; i <= MAXN; i++) { if( !check[i] ) { prime[tot++] = i; mu[i] = -1; } for(int j = 0; j < tot; j ++) { if( i * prime[j] > MAXN) break; check[i * prime[j]] = true; if( i % prime[j] == 0) { mu[i * prime[j]] = 0; break; } else { mu[i * prime[j]] = -mu[i]; } } }}int sum[MAXN+10];//找[1,n],[1,m]内互质的数的对数long long solve(int n,int m){ long long ans = 0; if(n > m)swap(n,m); for(int i = 1, la = 0; i <= n; i = la+1) { la = min(n/(n/i),m/(m/i)); ans += (long long)(sum[la] - sum[i-1])*(n/i)*(m/i); } return ans;}int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); Moblus(); sum[0] = 0; for(int i = 1;i <= MAXN;i++) sum[i] = sum[i-1] + mu[i]; int a,b,c,d,k; int T; scanf("%d",&T); while(T--) { scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); long long ans = solve(b/k,d/k) - solve((a-1)/k,d/k) - solve(b/k,(c-1)/k) + solve((a-1)/k,(c-1)/k); printf("%lld\n",ans); } return 0;}