| Submit | All submissions | Best solutions | Back to list |
ADAGCD - Ada and GCD |
Ada the Ladybug got interesting homework. She had to count gcd of a few numbers. As she is a great mathematician, she done it in meanwhile (in fact, she submited it during the class it was assigned in). The teacher was impressed so he gave Ada a bonus homework (for bonus points). It is same as previous one with a little difference - there are bigger numbers.
Since the number are too large to be written as numbers, they are written as product of lesser numbers. Find their gcd.
Input
The first line of input consists of 2 ≤ N ≤ 106, the number of numbers for which Ada wants to find their gcd.
Each of the next N lines contains an integer 1 ≤ Mi < 106 followed by Mi integers, 1 ≤ Aj ≤ 107, the numbers whose product is the ith number.
The sum of all Mi won't exceed 106
Output
Print the gcd on a single line. Since this number might be pretty big, output it modulo 109+7 (1000000007)
Example Input 1
3 4 1 2 3 4 1 36 2 6 5
Example Output 1
6
Example Input 2
2 11 1 2 3 4 5 6 7 8 9 10 11 2 1024 15
Example Output 2
3840
| Added by: | Morass |
| Date: | 2017-02-11 |
| Time limit: | 2s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
hide comments
|
||||||
|
2018-11-22 20:59:15
Help! On 15 TC it gives NZEC . I Code in java. Any Type of Suggestion will be Appreciated. |
||||||
|
2017-07-27 22:19:01
easier version is http://www.spoj.com/problems/HG/ :) Last edit: 2017-07-27 22:19:15 |
||||||
|
2017-06-09 11:05:59 shubham
AC in one go.. :) |
||||||
|
2017-06-09 11:05:37 shubham
AC in one go.. :) |
||||||
|
2017-04-14 13:08:17
@morass : can you check my solution? *_* Found the bug myself! The irony is, i found the bug in my template which gave wrong for large numbers which i cannot find before,while solving another problem today i found that bug and revisited this problem after 1 month to get an AC :) Last edit: 2017-04-25 16:36:04 |
||||||
|
2017-04-11 22:26:47
@candide: Good day to you I modified the sentence - please check whether it makes more sense now ^-^ Have nice day! |
||||||
|
2017-04-11 13:06:46 candide
Bad description problem. Introduction characters (Ada, his teacher, etc) is only noise and doesn't help question understanding. "Each of the next N lines contains an integer 1 ≤ Mi < 10^6 followed by Mi integers, 1 ≤ Aj ≤ 10^7, the divisors of number i, whose product is the number i." : i is an index so the sentence is meaningless. More, the Mi's are some divisor (not all the divisors) and finally we dont care of that since the product of those numbers gives the integer you are talking about. |
||||||
|
2017-02-26 12:11:20
@[Lakshman]: Good day to you. Well in fact on every line there is a "big" number, which is product of the numbers on the line and you are supposed to find their gcd. Consider first test-case: 3 4 1 2 3 4 = 1*2*3*4 ==24 1 36 = 36 2 6 5 = 6*5 == 30 gcd(24,36,30)==6 Good Luck & Have Nice Day |
||||||
|
2017-02-26 09:45:32 [Lakshman]
I am not getting this problem, can you please explain the sample test cases. |
||||||
|
2017-02-22 11:13:10
@Vipul Srivastava:: Hello, well there is just one test-case .. so you meant overall complexity? It is slightly complicated (since it is bound to prime arithmetic). Since I'm not a good mathematician I can tell you only STRONG BOUND which is O(Nlog(|Ai|)log(sqrt(N))) .. but both the logarithms are "weak" (if I can call it this way) Anyway there are a few "kinds" of "numbers" which behave differently (depending on decomposition of "M" over all "numbers") Good Luck & Have Nice Day |
||||||
RSS