hdu 1695（歐拉函數+容斥原理）

題意： 在區間[a,b]中選擇一個數，在區間[c,d]中選擇一個數  問這兩個數的gcd值為k有多少個

分析：我們找gcd為k的數并不好找，但找gcd為1的數就好找的多我們把b/=k,d/=k就變成在區間内找gcd值為1的個數了，此外我們注意到本題可以假設a c為1  是以區間就是[1,b]    [1,d]  我們可以分成區間[1,b] 和區間[b+1,b]兩部分  在前一部分隻需要求出沒個數的歐拉函數值累加起來即可，後一個區間中找出一個數與前一個區間中的數互質即可，我們利用容斥原理，

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <vector>
#include <string>
#include <utility>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;
struct sa{
    int k;
    int fec[20];
}p[100005];
long long phi[100005];
void euler(){
    phi[1]=1;
    for(int i=1;i<100005;i++)
    p[i].k=0;
    for(int i=2;i<100005;i++){
        if(!phi[i]){
            for(int j=i;j<100005;j+=i){
                if(!phi[j])phi[j]=j;
                phi[j]=phi[j]*(i-1)/i;
                p[j].fec[p[j].k]=i;
                p[j].k++;
            }
        }
        phi[i]+=phi[i-1];
    }
}//利用遞推公式一邊求歐拉函數，一邊把每個數質因子分解
long long solve(int id,int b,int n){
    long long sum=0,t;
    for(int i=id;i<p[n].k;i++){
        t=b/p[n].fec[i];
        sum+=t-solve(i+1,t,n);
    }
    return sum;
}//遞歸實作容斥原理
int main(){
    euler();
    int m=1;
    int a,b,c,d,k;
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        if(k==0){
            printf("Case %d: 0\n",m++);
            continue;
        }
        b/=k;
        d/=k;
        if(b>d)swap(b,d);//交換兩個數，使得b<d
        long long sum=phi[b];
        for(int i=b+1;i<=d;i++){
            sum+=b-solve(0,b,i);
        }
        printf("Case %d: %I64d\n",m++,sum);
    }
    return 0;
}
           

先将x進行質因子分解，然後，在[1,b]中找到能被x質因子整除的個數，用b-減去這個數就行了。