Puppy and GCD
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
One fine sunny day Tuzik was waiting for his master Vanka near their house. Time kept going by but the boy just wouldn't come out of the house. "Oh no, maybe he is participating in some programming contest like Lunchtime again. If I help him, we can go and start playing some interesting game outdoors sooner." - thought Tuzik, so he went into the house.
Vanka was struggling with the last problem indeed. The statement was: "Given integers N and D, find how many pairs of integers (i, j) such that 1 ≤ i ≤ j ≤ N have the greatest common divisor exactly D."
"LOL, even I can solve it faster than him." - thought Tuzik. Unfortunately he is just a little puppy so he can't explain or code up the solution. But he wants to go outdoors with his master, so please help Vanka solve this problem for Tuzik's sake.
The first line contains one integer T denoting the number of test cases.
The following T lines contain two space-separated integers each: N and D - description of each test case.
For each test case, output a single line containing the answer for this test case.
- 1 ≤ T ≤ 10
- 1 ≤ N, D ≤ 5*108
- Subtask #1[20 points]: 1 ≤ N, D ≤ 500
- Subtask #2[25 points]: 1 ≤ N, D ≤ 105
- Subtask #3[25 points]: 1 ≤ N, D ≤ 2*108
- Subtask #4[30 points]:1 ≤ N, D ≤ 5*108
Input: 1 12 3 Output: 6
6 such pairs: (3, 3), (3, 6), (3, 9), (3, 12), (6, 9), and (9, 12).
|Tags||ltime26, math, number-theory, pavel1996|
|Time Limit:||4 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions