https://acm.khpnets.info/w39/index.php?action=history&feed=atom&title=%D0%9C%D0%BE%D0%B4%D1%83%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%B0%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B0Модульная арифметика - История изменений2026-05-13T11:41:47ZИстория изменений этой страницы в викиMediaWiki 1.39.3https://acm.khpnets.info/w39/index.php?title=%D0%9C%D0%BE%D0%B4%D1%83%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%B0%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B0&diff=2769&oldid=prevCtrlalt: Новая страница: «== Основные арифметические операции == * (A + B) % MOD = (A % MOD + B % MOD) % MOD * (A - B) % MOD = ((A % MOD - B % MOD) % MOD + MO...»2022-04-02T17:59:18Z<p>Новая страница: «== Основные арифметические операции == * (A + B) % MOD = (A % MOD + B % MOD) % MOD * (A - B) % MOD = ((A % MOD - B % MOD) % MOD + MO...»</p>
<p><b>Новая страница</b></p><div>== Основные арифметические операции ==<br />
* (A + B) % MOD = (A % MOD + B % MOD) % MOD<br />
* (A - B) % MOD = ((A % MOD - B % MOD) % MOD + MOD) % MOD<br />
* (A * B) % MOD = ((A % MOD) * (B % MOD)) % MOD<br />
<br />
== «Деление» и нахождение обратного элемента ==<br />
* (A / B) % MOD = ((A % MOD) * B<sup>-1</sup>) % MOD<br />
:* Если MOD простой: B<sup>-1</sup> = B<sup>MOD - 2</sup> % MOD<br />
:* Если B и MOD взаимно просты: B<sup>-1</sup> = X, где gcdex(B % MOD, MOD, X, Y) == 1<br />
:* Если B и MOD не взаимно просты, решения не существует.<br />
<br />
<br />
class ModInt {<br />
long long value;<br />
static const long long mod = 1e9 + 7;<br />
<br />
static long long gcdex(long long a, long long b, long long &x, long long &y) {<br />
if (!b) {<br />
x = 1;<br />
y = 0;<br />
return a;<br />
}<br />
long long x1, y1, d = gcdex(b, a % b, x1, y1);<br />
x = y1;<br />
y = x1 - a / b * y1;<br />
return d;<br />
}<br />
<br />
public:<br />
ModInt(long long value = 0) : value((value % mod + mod) % mod) {}<br />
<br />
ModInt operator + (const ModInt &that) const {<br />
return value + that.value;<br />
}<br />
<br />
ModInt operator - (const ModInt &that) const {<br />
return value - that.value;<br />
}<br />
<br />
ModInt operator * (const ModInt &that) const {<br />
return value * that.value;<br />
}<br />
<br />
ModInt operator / (const ModInt &that) const {<br />
long long x, y;<br />
gcdex(that.value, mod, x, y);<br />
return value * x;<br />
}<br />
<br />
bool canDivide(const ModInt &that) const {<br />
long long x, y;<br />
return that.value && gcdex(that.value, mod, x, y) == 1;<br />
}<br />
<br />
friend istream &operator >> (istream &in, ModInt &m) {<br />
long long value;<br />
in >> value;<br />
m = ModInt(value);<br />
return in;<br />
}<br />
<br />
friend ostream &operator << (ostream &out, const ModInt &m) {<br />
return out << m.value;<br />
}<br />
};<br />
<br />
== Ссылки ==<br />
Теория:<br />
* [http://e-maxx.ru/algo/reverse_element e-maxx.ru — Обратный элемент в кольце по модулю]<br />
* [https://cp-algorithms.com/algebra/module-inverse.html cp-algorithms.com — Modular Inverse]<br />
* [https://brestprog.by/topics/modulo/ brestprog.by — Операции по модулю]<br />
* algorithmica.org — Модульная арифметика, обратный элемент: [https://wiki.algocode.ru/index.php?title=%D0%9C%D0%BE%D0%B4%D1%83%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%B0%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B0 1] [https://algorithmica.org/ru/reciprocal 2] [https://ru.algorithmica.org/cs/modular/reciprocal/ 3] [https://wiki.algocode.ru/index.php?title=%D0%9E%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE_%D0%BB%D1%8E%D0%B1%D0%BE%D0%BC%D1%83_%D0%BC%D0%BE%D0%B4%D1%83%D0%BB%D1%8E_%D0%B2_2_%D1%81%D1%82%D1%80%D0%BE%D1%87%D0%BA%D0%B8 4]<br />
* [https://usaco.guide/gold/modular?lang=cpp usaco.guide — Modular Arithmetics]<br />
* [https://codeforces.com/blog/entry/72527 codeforces.com — Modular Arithmetic for Beginners]<br />
Код:<br />
* [https://github.com/indy256/codelibrary/blob/master/cpp/numbertheory/modint.h indy256/codelibrary/cpp/numbertheory/modint.h]<br />
<br />
[[Категория: Математика]]</div>Ctrlalt