MANJFIRE - Manoj and Fire

no tags 

Manoj is a geek who loves ciphering data. He is also known for doing stupid things like setting fire in his room like a caveman. One day he does that and accidentally throws a paper containing some sensitive information. However, he has the encrypted version of the data. 

Each number in the original text is the number of pairs of integers A,B (A<B, 1 <= A,B <= N) such that their GCD Quotients match the given set of integers.

GCD Quotients of a pair (A,B) is defined as the sequence of quotients that are obtained while computing the gcd of A and B using Euclid's Algorithm. For example, 

          GCD(7,9) = 
GCD(7,9) = 7) 9 (1 7 --- 2) 7 (3 6 --- 1) 2 (2 2 --- 0 ---

In the above example, the gcd quotient sequence is [1,3,2]


The first line contains T, the number of test cases. Each test case contains two integers N and Q on the first line and Q integers on the second line, denoting the quotient sequence.


For each test case, output the number of pairs of integers, whose gcd quotient sequence match with the given sequence.


10 3
1 3 2
2 1


For the first case, there exists only one such pair in the range [1,10], which is (7,9). 
For the second case, the smallest possible pair is (1,3), but since the given range is only [1,2],
hence we have zero such pairs.
1 <= N <= 1016
1 <= Q <= 50
1 <= each quotient value <= 1000
1 <= T <= 105
Product of all Quotient Values <= 1012
A new test file has been added that includes some tricky test cases on 29/09/14 and all submissions were rejudged.
Please don't ask the answers for additional test cases in the comments. Figure out yourself. 

hide comments
Apoorv Agarwal: 2014-10-02 13:32:20

Finally found the tricky case!! :D
Btw a nice one! Enjoyed solving!

shiv prasad chabarval: 2014-10-01 14:15:13

can't figure out why WA :(
checked all corner cases for (a<b)

Andy: 2014-10-01 14:15:13

--nitish--> Nice Catch.

Last edit: 2014-09-30 15:04:18
Jacob Plachta: 2014-10-01 14:15:13

Haha, nice "tricky case", I'm glad that was added.

--nitish--> Thanks :).

Last edit: 2014-09-30 14:59:09
ping_of_death: 2014-10-01 14:15:13

@nitish can u give any hint for tricky test case.

Andy: 2014-10-01 14:15:13

--nitish--> Fixed the test case.

Last edit: 2014-09-29 21:42:36
Rahul Jain: 2014-10-01 14:15:13

I don't think if there is anything wrong in my code as long as you didn't take any value less than 1.

Rahul Jain: 2014-10-01 14:15:13

@Nitish, did u take any quotient value or any other value=0 ?

Last edit: 2014-09-29 12:10:29

Added by:nitish rao
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:My own Problem