Practice on Toph

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

Beauty of AP

By prodip_bsmrstu · Limits 1.5s, 512 MB

Solving problems is fun in competitive programming, right? So let’s solve a fun task today too :P.

16th December, the day of victory, a memorable day for our nation. You have planned to celebrate the day with some of your friends by inviting them to your home. Well, the nice initiative! But the number of friends to invite not fixed yet. After a while, a peculiar idea comes into your mind.

You take a piece of paper and a pencil and started to write an Arithmetic Progression (AP). The first term of this progression is a and the common difference between every two adjacent terms is d. So if we write the n terms of the sequence from left to write and named them as S = s1, s2, s3, …. sn, then the sequence will be, s1 = a, s2 = a + d, s3 = a + 2d, s4 = a + 3d ….. sn = a + (n - 1) d.

You defined a prefix of length L (1 ≤ L ≤ n) (first L consecutive numbers) of this AP as good if the following conditions hold

  • If L = 1 or,
  • for every pair of i, j where **1≤_i, j_ ≤L**, if **i !=j** then **(si % L != sj % L)**.

You always want to invite your friends in such a way that if you invite k of your friends then the prefix of length k of the aforementioned AP has to be good.
Count in how many ways you can invite your friends.
You have to Count this for several cases.

Input

First-line will contain a number T, denoting the number of test cases.
Every successive case will contain three numbers a, d and n, where a is the first term of the AP,
d is the common difference and n is the number of terms in the AP.

Constraints:

1 <= T <= 2000
1 ≤ a, n ≤ 1018
1 ≤ d ≤ 1012

Output

In every test case, print a single integer, the number of ways to invite friends . Don’t forget to print a new line after every test case.

Sample

InputOutput
1
3 2 5
3

Explanation:
There are 5 terms in the sequence. They are: 3, 5, 7, 9, and 11. For every length (from 1 to 5) of prefix we get the following sequence:

For L = 1, S = (3 % 1 = 0) = (0).

For L = 2, S = (3 % 2 = 1, 5 % 2 = 1) = (1, 1).

For L = 3, S = (3 % 3 = 0, 5 % 3 = 2, 7 % 3 = 1) = (0, 2, 1)

For L = 4, S = (3 % 4 = 3, 5 % 4 = 1, 7 % 4 = 3, 9 % 4 = 1) = (3, 1, 3, 1).

For L = 5, S = (3 % 5 = 3, 5 % 5 = 0, 7 % 5 = 2, 9 % 5 = 4, 11 % 5 = 1) = (3, 0, 2, 4, 1).

So for L = 1, 3 and 5 we get the desired output. So the answer is 3.


Note

Data set is huge, use faster input output.

Discussion

Statistics


75% Solution Ratio

EgorKulikovEarliest, Dec '19

ashikurrahmanFastest, 0.1s

EgorKulikovLightest, 131 kB

kzvd4729Shortest, 921B

Submit

Login to submit

Editorial

https://forthright48.com/euler-totient-or-phi-function from this link see the section &quot;Theorem ...

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