Troubles with segtree problem

Правка ru4, от ivanz, 2020-11-02 12:28:59

Hello! Could you please explain to me why my 94709653 gets WA4 in 1422F - Скучные запросы? 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!!!

Теги #help me, segment tree, number theory, hard problem

История

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