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

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.

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.**

1 <= T <= 2000

1 ≤ a, n ≤ 1018

1 ≤ d ≤ 1012

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.

Input | Output |
---|---|

1 3 2 5 | 3 |

Explanation: 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. |

Data set is huge, use faster input output.

75% Solution Ratio

EgorKulikovEarliest,

ashikurrahmanFastest, 0.1s

EgorKulikovLightest, 131 kB

kzvd4729Shortest, 921B

Login to submit

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

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