zcmimi's blog

arrow_back逆元共3篇文章

avatar
zcmimi
2019-01-21 11:31:55

转自https://www.cnblogs.com/hadilo/p/5914302.html

欧几里得

定义:

gcd(a,b)为整数ab的最大公约数

引理:

gcd(a,b)=gcd(b,a \bmod b)

证明:

设$r=a \b

avatar
zc
2020-02-08 22:00:00
查看原题

点击跳转

假设我们要求的是A\cdot B \equiv 1 \pmod{x^n},

我们已经求出了B'满足A\cdot B' \equiv 1 \pmod{x^\frac n2}

\because A\cdot B \equiv 1 \pmod {x^n} \\ \because A\cdot B' \equiv 1 \pmod{x^\frac n2} \\ \therefore A \cdot (B-B') \equiv 0 \pmod{x^\frac n2} \\ \therefore B-B' \equiv 0 \pmod{x^\frac n2} \\ (B-B')^2 \equiv 0 \pmod{x^n} \\ B^2-2BB'+B'^2 \equiv 0 \pmod{x^n} \\ \therefore A(B^2-2BB'+B'^2) \equiv 0 \pmod{x^n} \\ AB^2-2ABB'+AB'^2 \equiv 0 \pmod{x^n} \\ \because A\cdot B \equiv 1 \pmod {x^n} \\ \therefore B-2B'+AB'^2\equiv 0 \pmod{x^n} \\ B\equiv 2B'-AB'^2 \pmod{x^n}

于是我们可以用倍增+NTT解决(复杂度\mathcal{O(n \log^2 n)})

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

这个题解棒棒哒

答案就是C(n+m,m)-C(n+m,m-1)

1/1
Search
search