Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N. 
Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than 1 or, equivalently, if their greatest common divisor is 1. The number 1 is relatively prime to every integer.

2

1 10 2

3 15 5

Case #1: 5

Case #2: 10

In the first test case, the five integers in range [1,10] which are relatively prime to 2 are {1,3,5,7,9}.

 题目大意：给你3个数A,B,C,让你求出从A到B的所有数字中与C互质的个数，
题解：直接求互质不好求，我们就求与C不互质的个数，然后最后在减去就可以了

#include<iostream>

#include<cstdio>

#include<vector>

#include<cstring>

using namespace std;

typedef long long ll;

const int N=1E5+;

ll arr[N];

vector<ll >ve;

int main(){

    int t,k=;

    scanf("%d",&t);

    while(t--){

        k++;

        ll a,b,c,pos=;

        scanf("%lld%lld%lld",&a,&b,&c);

        for(int i=;i*i<=c;i++){

            if(c%i==){

                pos++;

                ve.push_back(i);

                while(c%i==) c/=i;

            }

        }

        if(c>)

        {

            pos++;

            ve.push_back(c);

        }

        ll sa=,sb=;

        for(ll i=;i<(<<pos);i++){

            ll sum=,cnt=;

            for(ll j=;j<pos;j++){

                if(&(i>>j)){

                    sum*=ve[j];

                    cnt++;

                }

            }

            if(cnt&){//容斥里的奇减偶加

                sa+=(a-)/sum;//a-1前有多少个数字是sum的倍数，

                sb+=(b)/sum;

            }

            else {

                sa-=(a-)/sum;

                sb-=(b)/sum;

            }

        }

        sb=sb-sa;//应题目要求  从A到B

        printf("Case #%d: %lld\n",k,b-a+-sb);

        ve.clear();

    }

    return ;

}