既求gcd(b/k,d/k)==1的组合的个数,

设B=b/k  D=d/k 且 B<D

考虑从D中取一个数

如果在1~B这部分可由欧拉phi函数求得,若在B+1~D这部分,可以用容斥原理求得.

GCD

2
1 3 1 5 1
1 11014 1 14409 9

Case 1: 9
Case 2: 736427

Hint
For the first sample input, all the 9 pairs of numbers are (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5).
 

/* ***********************************************
Author        :CKboss
Created Time  :2015年03月27日 星期五 09时27分50秒
File Name     :HDOJ1696.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

typedef long long int LL;

const LL maxn=100100;

LL a,b,c,d,k;

LL phi[maxn+10];
LL sum[maxn+10];

vector<LL> prime[maxn+10];

void phi_table(LL n)
{
	phi[1]=1;
	for(LL i=2;i<=n;i++)
	{
		if(!phi[i])
		{
			for(LL j=i;j<=n;j+=i)
			{
				if(!phi[j]) phi[j]=j;
				phi[j]=phi[j]/i*(i-1);
				prime[j].push_back(i);
			}
		}
	}
}

LL RET;

void dfs(int x,LL b,LL now,LL mark)
{
	for(int i=x,sz=prime[now].size();i<sz;i++)
	{
		LL p=prime[now][i];
		RET+=mark*(b/p);
		if(x+1<sz) dfs(i+1,b/p,now,-mark);
	}
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

	phi_table(maxn);
	for(LL i=1;i<=maxn;i++) sum[i]=sum[i-1]+phi[i];

	LL T_T,cas=1;
	cin>>T_T;
	while(T_T--)
	{
		cin>>a>>b>>c>>d>>k;
		if(k==0)
		{
			cout<<"Case "<<cas++<<": 0"<<endl;
			continue;
		}
		b/=k; d/=k;
		if(b>d) swap(b,d);
		LL ans=sum[b];

		for(LL i=b+1;i<=d;i++)
		{
			RET=b; dfs(0,b,i,-1);
			ans+=RET;
		}

		//printf("Case %lld: %lld\n",cas++,ans);
		cout<<"Case "<<cas++<<": "<<ans<<endl;
	}
    
    return 0;
}

HDOJ 1695 GCD phi函数+容斥原理

原文：http://blog.csdn.net/ck_boss/article/details/44674049