HDU 1695 GCD (欧拉函数，容斥原理)

2
1 3 1 5 1
1 11014 1 14409 9

Case 1: 9
Case 2: 736427
对于求x在1~n之间，y在1~m之间的gcd(x,y)=k;就相当于求x在1~n/k之间，y在1~m/k之间的gcd(x,y)=1;即x,y互质的对数对于欧拉函数，可以求比n小的和n互质的个数。而容斥原理可以求1~指定范围，和n互质的个数。所以我们枚举一个区间的数，然后求这个数在另一个区间的互质的个数。容斥原理可以解决，但是为了学习熟悉欧拉函数，所以可以分成两段，一段用欧拉函数，另一段用容斥原理。
求解欧拉函数，可以用线性素数晒求解，这样同时打了一个素数表，为容斥原理服务
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <bitset>

using namespace std;
typedef long long int LL;
#define MAX 1000000
bool check[MAX+5];
LL fai[MAX+5];
LL prime[MAX+5];
LL sprime[MAX+5];
LL q[MAX+5];
int cnt;
void eular()//线性筛求解欧拉函数
{
	memset(check,false,sizeof(check));
	fai[1]=1;
	int tot=0;
	for(int i=2;i<=MAX+5;i++)
	{
		if(!check[i])
		{
            prime[tot++]=i;
			fai[i]=i-1;
		}
		for(int j=0;j<tot;j++)
		{
			if(i*prime[j]>MAX+5) break;
			check[i*prime[j]]=true;
			if(i%prime[j]==0)
			{
				fai[i*prime[j]]=fai[i]*prime[j];
				break;
			}
			else
			{
				fai[i*prime[j]]=fai[i]*(prime[j]-1);
			}
		}
	}
}
void Divide(LL n)//分解质因子
{
    cnt=0;
    LL t=(LL)sqrt(1.0*n);
    for(LL i=0; prime[i]<=t; i++) {
        if(n%prime[i]==0) {
            sprime[cnt++]=prime[i];
            while(n%prime[i]==0)
                n/=prime[i];
        }
    }
    if(n>1)
        sprime[cnt++]=n;
}
LL Ex(LL n)//容斥原理之队列实现
{
    
    LL sum=0;
    LL t=1;
    q[0]=-1;
    for(LL i=0; i<cnt; i++) {
        LL x=t;
        for(LL j=0; j<x; j++){
            q[t]=q[j]*sprime[i]*(-1);
            t++;
        }
    }
    for(LL i=1; i<t; i++)
        sum+=n/q[i];
    return sum;
}
int main()
{
	int t;
	scanf("%d",&t);
	eular();
	int cas=0;
	int a,b,c,d,k;
	while(t--)
	{
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
		if(k==0||k>b||k>d)
		{
			printf("Case %d: 0\n",++cas);
			continue;
		}
		if(b>d) swap(b,d);
		b/=k;d/=k;
		LL ans=0;
		for(int i=1;i<=b;i++)
             ans+=fai[i];
		for(int i=b+1;i<=d;i++)
		{ Divide(i);ans+=(b-Ex(b));}
		printf("Case %d: %lld\n",++cas,ans);
	}
	return 0;

}