数論
合同式
拡張ユークリッド互除法でa×x≡b (mod m)の全解を正準剰余として求めます。
- TIME
- O(log m + g log m)
- SPACE
- O(g)
m = 法、g = gcd(a,m) / 上限: |a|,|b|≤10⁹、1≤m≤100,000
a*x ≡ b (mod m) を解きます。
数論
拡張ユークリッド互除法でa×x≡b (mod m)の全解を正準剰余として求めます。
m = 法、g = gcd(a,m) / 上限: |a|,|b|≤10⁹、1≤m≤100,000
a*x ≡ b (mod m) を解きます。