LGLOVE - LCM GCD Love
Bob fell in love with LCM and GCD. So much that he started seeing LCMs and GCDs everywhere. Betty, his girlfriend was jealous and she gave Bob an array A[ ] of integers, which had nothing to do with LCMs or GCDs.
Quickly, naughty Bob evaluated a new array B[ ] containing n integers, such that B[i] is LCM(1, 2, 3 ... A[i]), A[i]>0. When A[i] is 0, B[i] is also 0.
Angry Betty decided to give m queries to Bob, each being one of the following type:
- "0 i j p", meaning add 'p' to each element in A[i...j]. -300000 <= p <= 300000, 0 <= i <= j < n
- "1 i j", meaning print the LCM of all elements in B[i...j]. 0 <= i <= j < n
- "2 i j", meaning print the GCD of all elements in B[i...j]. 0 <= i <= j < n
Input
First line contains n (n <= 100000) and m (m <= 35000).
Second line contains n integers in the original array A[ ].
Next m lines contain one of the above said queries.
It is guaranteed that A[i] after any number of updates will satisfy 0 <= A[i] <= 300000.
Output
Output one line for each query of type 1 or 2, modulo 1000000007.
Example
Input: 5 5 4 1 3 6 2 1 2 4 2 1 3 0 0 3 2 1 1 2 2 2 4 Output: 60 1 60 2
hide comments
maikelele:
2020-05-07 08:28:05
Can anyone explain this part, "Output one line for each query of type 1 or 2, modulo 1000000007." ??
|
|
Sigma Kappa:
2018-06-14 01:14:38
When pre-computing all the LCMs, do we make use of recurrence lcm[x] = lcm[x-1]*x*modular_inverse(gcd(lcm[x-1],x)) % MOD? Last edit: 2018-06-18 22:05:48 |
|
Jaswanth:
2015-09-06 04:32:49
@Prof_Utonium_ಉಮೆಶ್: can u tell where my solution is going wrong. submission id=15069964 |
|
californiagurl:
2014-12-22 18:57:36
anybody else getting SIGSEGV? :/ |
|
Damian Straszak:
2012-05-27 11:55:18
the outputs are incorrect, only a wrong solution can pass
|
|
Walrus:
2012-02-06 08:02:27
and gcd(0,i) = 0 or i?
|
|
Ehor Nechiporenko:
2010-10-07 16:30:54
0 0 |
|
ymGXX:
2010-10-07 03:55:11
gcd(0,0)=?
|
Added by: | Prof_Utonium_ಉಮೆಶ್ |
Date: | 2010-10-05 |
Time limit: | 0.108s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 JS-RHINO OBJC SQLITE |
Resource: | MNNIT IOPC 2010 , Co-author: ashish_pant |