Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Numbers Tell

By ridowan007 · Limits 2s, 1.0 GB

Ok, so in this problem, you will be given N and M, how many ways we can take two numbers from 1 to N so that their absolute difference is divisible by M. As the answer can be quite big, give the modulo of the answer by 1000,000,009.


First line of the input is T(T ≤ 100000), then T test cases follows. Each case have only one line containing two positive integers N and M (1 ≤ N, M ≤ 1018).


For each test case, output a line containing "Case I: d" where I is test case number and d is the answer modulo by 1000000009.


4 3
7 5
Case 1: 1
Case 2: 2

In the first case, There we can only take 1 and 4 between 1 to 4 whose difference 3 is divisible by 3.
For second case the pairs are (1, 6) and (2, 7).

Note: Based on a true chat.



45% Solution Ratio

Double_OEarliest, Apr '18

raiyan.sidneFastest, 0.0s

Double_OLightest, 2.2 MB

raiyan.sidneShortest, 301B


Login to submit

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.