Pro.ID21685 TitleGCD Title链接http://10.20.2.8/oj/exercise/problem?problem_id=21685 AC3 Submit7 Ratio42.86% 时间&空间限制描述The greatest common divisor GCD(a, b) of two positive integers a and b, sometimes written (a, b), is the largest divisor common to a and b. For example, (1, 2) = 1, (12, 18) = 6. (a, b) can be easily found by the Euclidean algorithm. Now Carp is considering a little more difficult problem: Given integers N and M, how many integer X satisfies 1 ≤ X ≤ N and (X, N) ≥ M. 输入The first line of input is an integer T ( T ≤ 3000 ) representing the number of test cases. The following T lines each contains two numbers N and M ( 1 ≤ N ≤ 1000000000, 0 ≤ M ≤ 1000000000 ), representing a test case. 输出Description The greatest common divisor GCD(a, b) of two positive integers a and b, sometimes written (a, b), is the largest divisor common to a and b. For example, (1, 2) = 1, (12, 18) = 6. (a, b) can be easily found by the Euclidean algorithm. Now Carp is considering a little more difficult problem: Given integers N and M, how many integer X satisfies 1 ≤ X ≤ N and (X, N) ≥ M. Input The first line of input is an integer T ( T ≤ 3000 ) representing the number of test cases. The following T lines each contains two numbers N and M ( 1 ≤ N ≤ 1000000000, 0 ≤ M ≤ 1000000000 ), representing a test case. Output For each test case, output the answer on a single line. Sample Input 3 Sample Output 1 Source 样例输入3 样例输出1 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-3 15:15 , Processed in 0.028864 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
