TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4494
  • Problem
  • P4494找互质
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s,128m
    Description

    给一个整数n,请你在指定区间[a,b]中找出共有多少个数是与n互质的。

    Input Format

    一行,三个整数a,b,n

    Output Format

    一行,一个整数,表示计算结果

    Sample Input 1

    1 10 2

    Sample Output 1

    5

    Sample Input 2

    3 15 5

    Sample Output 2

    10

    Hint

    1 <=  a <= b <= 10^15
    1 <= n <= 10^9


    Source  hdu4135