December Long14 problem understanding Sereja and GCD

general
,
1

In december long14, problem Sereja and GCD

Example

Input:

2

5 5 1 5

5 5 4 5

Output:

3125

2

How is the first answer 3125?

As per my understanding,

N=5,M=5 hence number of permutations of 5 elements from set [1,2,3,4,5].

L=1,R=5 so, D=1,2,3,4,5.

Thus for D=1, required array is =>[1,2,3,4,5], no of permutations = 120.

For D=2, required array is =>[2,4], no of permutations = 2.

For D=3, required array is =>[3], no of permutations = 1.

For D=4, required array is =>[4], no of permutations = 1.

For D=5, required array is =>[5], no of permutations = 1.

Total =120+2+1+1+1=125.

Please correct me if I am wrong.

PS: If the answer reveals strategy than please do not answer.

2

you are missing some computations for D=1 , find it out yourself . for rest values of D answers are right .

3

I think this is related to more test cases discussion…

From my point of view there are only trivial cases in problem statement (for this problem).

N=5, M=5 so there 55 possibilities and all of those have gcd in range 1-5, so 55 is the answer…

Writing how many options are there for each D would be too much I think, so you have to find yourself, where you are wrong :wink:

4

@mediocoder, you understood the question wrong. In all the permutations which you consider, the length of the array must always be N (in this case, 5). The arrays you have specified have length less than 5. Also, integers can be repeated within the same array without any restriction, as long as the array satisfies the specified conditions. Hence, as you must have understood, you have missed a lot of cases.

2 Likes
5

@gvaibhav21
Thank you for pointing out mistakes in my understandings, it has been very helpful

1 Like
6

@betlista :diamonds::diamonds:

Thank you for explaining nicely, it has been very helpful.

1 Like
7

you’re welcome :slight_smile:

1 Like
8

i guess he is missing some conditions for D=2 too ???
am i right!!!

9

@grvana no

10

well, the main thing is that the arrays he has mentioned are themselves wrong, since the length of the arrays must be 5.

11

exactly
then for d=2
there can be
[2,4,4,4,4][4,2,4,4,4][4,4,2,4,4]… and so on
so how can there be only two arrays mentioned in the answer.
correct me if i’m wrong

12

@grvana you are right , i was mistaken

13

koi ni hota hai:)
these are the reasons im not able too solve it… lots of facts were unclear

1 Like