LCPC11B  CoPrime
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 coprime 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 Specification
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 <= 1015) and (1 <= N <= 109).
Output Specification
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
In the first test case, the five integers in range [1,10] which are relatively prime to 2 are {1,3,5,7,9}.
hide comments
Kushal Saharan:
20140624 15:16:01
Good Question! Learnt something new :) 

nbcool:
20130203 09:23:52
Is anybody getting TLE in this code


saivikneshwar:
20121126 12:19:32
This problem is pretty similar to HNUMBERS. 

Ehor Nechiporenko:
20121107 22:16:23
@Mehmet, HNUMBERS is very close to this problem, but simpler and has smaller constraints 

mehmetin:
20121107 14:10:54
Wasn't there a previous problem similar to this?


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121107 18:25:04
Fine, this problem is not tutorial :P Last edit: 20121107 18:24:59 

Ehor Nechiporenko:
20121106 22:09:12
Pretty simple task) Happy to resolve it first Last edit: 20121106 22:11:09 
Added by:  :P 
Date:  20121106 
Time limit:  0.293s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  LCPC2011 