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!!!
gcd(a, b) % MOD != gcd(a % MOD, b % MOD)
.
Yes but the lcm is not necessarily smaller than MOD.
.
solve(gcd(a % MOD, b % MOD), MOD) != solve(gcd(a, b), MOD) % MOD
.
The most important reason why you can't do this is this: if A divides B, A % MOD doesn't necessarily divide B % MOD. For example, 3 divides 6 but if you take MOD=4 3 doesn't divide 2. That's why operations like gcd and lcm break down when using MOD.