Co-prime

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 5526    Accepted Submission(s): 2209

Problem Description

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.

 

 

Input

The first line on input contains T (0 < T <= 100) the number of test cases, each of the next T lines contains three integers A, B, N where (1 <= A <= B <= 10

¹⁵) and (1 <=N <= 10

⁹).

 

 

Output

For each test case, print the number of integers between A and B inclusive which are relatively prime to N. Follow the output format below.

 

 

Sample Input

2 1 10 2 3 15 5

 

 

Sample Output

Case #1: 5 Case #2: 10

Hint

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

 

 

Source

 

/** @Author: lyuc* @Date:   2017-08-16 16:52:21* @Last Modified by:   lyuc* @Last Modified time: 2017-08-16 21:44:34*//* 题意：给你a,b,n让你求在区间[a,b]内有多少数与n互质 思路：求出n的所有质因子，然后[1,a]区间内的与n互质的数的数量就是，a减去不互质的数的数量，同理     [1,b]的也可以这么求,容斥求出这部分的结果*/#include 
     
      #define LL long long#define MAXN 1005#define MAXM 10005using namespace std;int t;LL a,b,n;LL factor[MAXN];LL tol;LL que[MAXM];void div(LL n){
   //筛出来n的因子    tol=0;    for(LL i=2;i*i<=n;i++){        if(n%i==0){            factor[tol++]=i;            while(n%i==0){                n/=i;            }        }    }    if(n!=1) factor[tol++]=n;//如果是素数的话加上本身}LL cal(LL x){
    //容斥计算出[1,x]内与n不互质的元素的个数    LL res=0;    LL t=0;    que[t++]=-1;    for(int i=0;i