链接：http://acm.hdu.edu.cn/showproblem.php?pid=1695

题意：在[a,b]中的x，在[c,d]中的y，求x与y的最大公约数为k的组合有多少。（a=1, a <= b <= 100000, c=1, c <= d <= 100000, 0 <= k <= 100000）

思路：由于x与y的最大公约数为k，所以xx=x/k与yy=y/k一定互质。要从a/k和b/k之中选择互质的数，枚举1~b/k，当选择的yy小于等于a/k时，能够选择的xx数为Euler(yy),当yy大于a/k时，就要用容斥原理来找到yy的质因数，在a/k范围内找到与yy互质的数。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <map>

#include <cstdlib>

#include <queue>

#include <stack>

#include <vector>

#include <ctype.h>

#include <algorithm>

#include <string>

#include <set>

#include <ctime>

#define PI acos(-1.0)

#define maxn 1<<20

#define INF 0x7fffffff

#define eps 1e-8

typedef long long LL;

typedef unsigned long long ULL;

using namespace std;

LL ans=0;

LL S=0;

LL sum2;

LL euler[100050];

void init()

{

    memset(euler,0,sizeof(euler));

    euler[1] = 1;

    for(int i = 2; i <= 100000; i++)

        if(!euler[i])

            for(int j = i; j <= 100000; j += i)

            {

                if(!euler[j])

                    euler[j] = j;

                euler[j] = euler[j]/i*(i-1);

            }

}

void factor(int n,int a[maxn],int b[maxn],LL &tt)

{

    int temp,i,now;

    temp=(int)((double)sqrt(n)+1);

    tt=0;

    now=n;

    for(i=2; i<=temp; i++)

    {

        if(now%i==0)

        {

            a[++tt]=i;

            b[tt]=0;

            while(now%i==0)

            {

                ++b[tt];

                now/=i;

            }

        }

    }

    if(now!=1)

    {

        a[++tt]=now;

        b[tt]=1;

    }

}

int dfs(int aa[],int pos,int res,int sum,int b,int tot)//res乘积，sum乘数的个数

{

    if(pos+1<=tot)

        dfs(aa,pos+1,res,sum,b,tot);

    sum++;

    res*=aa[pos];

    if(sum%2)

        sum2+=b/res;

    else

        sum2-=b/res;

    if(pos+1<=tot)

        dfs(aa,pos+1,res,sum,b,tot);

    return 0;

}

int main()

{

    int T,tt=0,aa[40],bb[40];

    init();

    while(~scanf("%d",&T))

    {

        tt=0;

        while(T--)

        {

            tt++;

            int a,b,c,d,k;

            scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);

            printf("Case %d: ",tt);

            if(k==0)

            {

                printf("0\n");

                continue;

            }

            if(d<b)

                swap(b,d);

            b/=k;

            d/=k;

            if(!b)

            {

                printf("0\n");

                continue;

            }

            ans=0;

            for(int i=1; i<=b; i++)

                ans+=euler[i];

            for(int i=b+1; i<=d; i++)

            {

                sum2=0;

                factor(i,aa,bb,S);

                dfs(aa,1,1,0,b,S);

                ans+=b-sum2;

            }

            printf("%I64d\n",ans);

        }

    }

    return 0;

}