I am trying to solve this problem, which provides an array of N integers , and requires to compute for M number of queries LCM of all the elements of the array in the range of indices [L,R] . As the answer can be very large print it modulo 10^9+7. 1<=M<=100000 1<=L<=R<=N. Please help to solve this problem.
Please provide a link to the problem.
Link was in the post.
Oops, right. My buggy CSS didn't highlight a link.
I have not found any information about the start and the end of the contest this problem is from on Hackerrank. It seems I need to sign up to see this, such a strange behaviour of the system. So I can't be sure the contest has ended, though I have some thoughts about the problem.
The contest has ended. For your convenience let me paste the problem statement here .
Problem Statement
vedaytas likes challenging professors at his school and this time he has challenged his mathematics professor. The professor was teaching a boring bookish method of calculating least common multiple of N integers.While he was mid-way explaining the procedure,vedaytas stood up and interrupted him and said that he had better way of performing the job.The aged professor felt offended at being interrupted in the middle and poses vedaytas a challenge that given list of N numbers,if he could answer his M queries correctly then he will be awarded with Ex-grade otherwise will be given a F-grade.Your job is very simple.Help vedaytas get an Ex-grade as for him now it is a matter of pride.
Query Format:
For each query vedaytas is given two numbers l and r (1-based indexing) and he needs to answer the lcm of the numbers at positions l,l+1,l+2,...,r
Input Format
First line contains T the number of test cases
For each test case we have the following information:
First line contains N the number of numbers in the list
Next line contains N space separated integers
Next line contains M the number of queries
Next M lines we have two space separated integers l and r
1<=T<=10
1<=N<=100000
1<=Number in the list<=10^9
1<=M<=100000
1<=L<=R<=N
NOTE : It is assured that the total number of queries in a test file doesnot exceed 10^5
I think this can help. For every prime, you need to maintain it's maximal power in the current segment. The overall number of prime divisors of all numbers in the input is . Futhermore, each number contains at most 9 different prime divisors. Using this, you can obtain some kind of solution in time.
I have solution in O(N * factorization(Amax) + MlogN).
Can you please elaborate your solution?
It's easier if you see lcm as product/gcd. Modulo being prime,you can use fermat's theorem ((x/y)%MODULO = ((x%MODULO)*((y^(MODULO-2))%MODULO))%MODULO But it seems that gcd modulo is not a good choice.
Another solution is using Mo's algorithm with complexity O(M*sqrt(n)*log*9).Log is for keeping the max value at every prime factor.
Your claim is true only for two numbers. For example, 6, 10, 15: their lcm is 30, but product/gcd is 900. Anyway, interested in faster solution.
My solution was based on rmq table,partitioning [l,r] in max log lcms and then doing lcm on them(two by two),but this doesn't work when things are made MODULO.
How will you compute the prime factorization of the numbers?
Polard P or Polard P-1?
Segment Tree
Not sure if this will be helpful.
Edit: I was completely incorrect. Sorry about misleading you!
This is probably the problem he is trying to solve: https://www.codechef.com/OCT15/problems/LOTERY
Check his submissions: https://www.codechef.com/users/thebruisedsoul
I got that problem accepted with just a regular LCM Segment tree.
This doesn't sound possible with a regular LCM segment tree, because of overflows... How did you deal with them?
https://www.hackerrank.com/contests/codex-15-0/challenges/lcm-challenge/submissions/code/3673250 I don't know if you can see the code, but it is really just a segment tree, where do you get overflows? Just calculate lcm as a*b/gcd(a,b)
Your code is not visible . Can you please share it on ideone or pastie?
http://pastie.org/private/ezhava8dy5u69jinwy33uw
You can't do LCMs reducing intermediate computations by MOD. Simple example:
3 8 500000004 8 1 1 3
lcm of all three numbers is clearly 1000000008 (= 1 mod 1000000007), but if you reduce intermediate computations you'll get a wrong answer, because you'll do lcm (8,500000004)=1, then lcm (1,8)=8.
The fact that your solution passes suggests that this clearly incorrect solution is also the model solution too. Shame on you, contest organizers!
Ouch, seems like it :P
Then, just ignore my comments, sorry for misleading.
can you please explain your approach to this?
Stop asking Codechef's solutions please!!
CodechefPolice, #CodeforcePolice
This is not a question from Codechef . This question is from a college contest on Hackerrank hosted a few days back(27th September). I have been trying to solve this question from past few days but keep getting WA or TLE.
.
.
can some one explain why this code dont work? thanks
I have a question. How can we deal with the problem of calculating $$$LCM(l, l + 1, ..., r)$$$ % $$$(1e9 + 7)$$$ with $$$r - l + 1 <= 1e6$$$ and $$$l, r <= 1e14$$$ (1 query only) ?
Thanks for reading <3 <3.
Put numbers $$$l$$$ through $$$r$$$ in an array and divide them by all the prime numbers up to $$$r - l + 1$$$, such that the remaining numbers would have only bigger prime factors (think of a fast way to do that, shouldn't be too hard). Take the product of the remaining numbers and multiply with the maximal exponent that you found for all the small primes. The idea is that if a prime factor bigger than $$$r - l + 1$$$ exists in the whole array, then it exists only once, so taking product of the remaining numbers is the same as taking product of the maximal exponents.