GCD not equal LCM
Time Limit: 1.0 s
Memory Limit: 256.0 MB
Description
We all know that,
GCD means Greatest Common Divisor. For example,
\(GCD ( 4, 10 , 12) = 2\), that means 2 is the largest possible number which divides all number appears in the set.
And, LCM means Least Common Multiple. For example,
\(LCM ( 4, 10, 12 ) = 60 \), that means 60 is the least common multiple of this set.
You are given two integers A and B. You need to find out all possible pair \((i , j)\) such that,
\(1 < = i <= A\) and \(1 < = j <= B,\)
- \(GCD ( i , j)\) ! = \(LCM ( i , j)\).
Note : ( "! = " means not equal.)
Input
First Line T, the number of test case.
In each test case, two postives integers A and B.
\(1 < = T < = 10^5\)
\(1 < = A , B < = 10^9\)
Output
In each test cases, print the total number of pair satisfy the conditions.
Sample
Input | Output |
---|---|
|
|
First test case explaination:
Only one pair satisfied this condition.
when i = 1 and j = 2,
GCD ( i, j ) = ( 1, 2 ) = 1.
LCM ( i, j ) = ( 1, 2 ) = 2.
GCD (i,j) ! = LCM ( i,j). So answer is 1.
Information
- ID
- 1075
- Difficulty
- 5
- Category
- Math | Number_Theory , Implementation Click to Show
- Tags
- # Submissions
- 18
- Accepted
- 13
- Accepted Ratio
- 72%
- Uploaded By
Related
In following contests: