Troubles with segtree problem

Revision en1, by ivanz, 2020-10-04 22:16:25

Hello! Could you please explain to me why my 94709653 gets WA4 in 1422F - Boring Queries? In my solution, I just use a segment tree to calculate lcm on the segment of the array. To calculate lcm of numbers a and b I use following fact: lcm(a, b) = a * b / gcd(a, b). Also, I take into account that we calculate lcm by modulo MOD. So lcm(a, b) = (((a * b) % MOD) * solve(gcd(a, b), MOD)) % MOD, where solve(x, m) returns such y that x * y ≡ 1 (mod m). Why it gets WA4? I think the idea is correct and I used verified patterns of segtree and functions loke gcd, lcm and solve (finding an inverse element in the residue ring modulo). Please help!!!

P.S. sorry for my poor English, I tried to use Grammarly and translator

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru4 Russian ivanz 2020-11-02 12:28:59 73
en4 English ivanz 2020-10-04 22:18:12 28
en3 English ivanz 2020-10-04 22:17:16 12 Tiny change: 'ts WA4 in [problem:' -> 'ts WA4 in the problem [problem:'
en2 English ivanz 2020-10-04 22:16:56 11 Tiny change: 'me why my [submissi' -> 'me why my submission [submissi'
en1 English ivanz 2020-10-04 22:16:25 755 Initial revision for English translation
ru3 Russian ivanz 2020-10-04 22:15:15 0 Мелкая правка: 'ts WA4 in [problem:1422F]? In my so' -> 'ts WA4 in problem? In my so'
ru2 Russian ivanz 2020-10-04 22:14:40 94
ru1 Russian ivanz 2020-10-04 22:11:52 661 Первая редакция (опубликовано)