Troubles with segtree problem

Revision ru1, by ivanz, 2020-10-04 22:11:52

Hello! Could you please explain me why my 94709653 gets WA4 in 1422F - Boring Queries? In my solution I just use segment tree to calculate lcm on segment of array. To calculate lcm of numbers a and b I use folowing 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 inverse element in the residue ring modulo). Please help!!!

Tags #help me, segment tree, number theory, hard problem

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 Первая редакция (опубликовано)