Luogu分析数论模板三合一?快速幂板子。exgcd 板子。BSGS 板子。然后注意要开 long long 。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #incl...
破解D-H协议$\begin{cases}g^a\equiv A\pmod{P}\\g^b\equiv B\pmod{P}\end{cases}$ 直接上 $\mathrm{BSGS}$ 求出 $a$ 和 $b$ ,然后答案就是 $g^{ab}\bmod P$ 。代码社交网络【模板】有向图矩阵树定理。代码交错序列首先推式子: $x^ay^b=(n-y)^ay^b=\sum\limits_{i...
LuoguBZOJ分析推式子+ $\mathrm{BSGS}$ 。已知 $X_{i+1}\equiv aX_i+b\pmod p$ 。两边加上 $\frac{b}{a}$ 后再乘上 $a$ ,变为 $aX_{i+1}+b\equiv a^2X_i+ab+b\pmod p$ 。那么就有 $X_{i+2}\equiv a^2X_i+ab+b\pmod p$ 。以此类推,可以得到 $X_{i}\e...
LuoguBZOJ分析$\begin{cases}g^a\equiv A\pmod{P}\\g^b\equiv B\pmod{P}\end{cases}$ 直接上$\mathrm{BSGS}$求出 $a$ 和 $b$ ,然后答案就是 $g^{ab}\mod P$ 。然后指数要对 $P-1$ 取膜而不是 $P$ ,因为 $\varphi(P)=P-1$ 。代码//It is made by M...
Luogu算法首先,我们可以把n个1写成$\frac{10^n-1}{9}$然后这个式子就变成了$\frac{10^n-1}{9}\equiv k \pmod m$$10^n-1\equiv 9k \pmod m$$10^n\equiv 9k+1 \pmod m$然后注意到$m$是质数,所以可以套上BSGS。和yyb一起学BSGS但是$m$最大有$10^{11}$,大概会爆long long...