又来到令人痛苦的latex环节了

P1082 同余方程

板子题，没什么好说的

这道题既是求同余方程，也是求逆元

板子如下：

long long gcd(long long a,long long b,long long &x,long long &y)
{
    if(b==0)
    {
        x=1;
        y=0; 
        return a;
    }else
    {
        long long k=gcd(b,a%b,x,y);
        swap(x,y);
        y-=(a/b)*x;
        return k;
    }
}

P1516 青蛙的约会

设两只青蛙跳跃\(a\)次后相遇

\[x+ma\equiv=y+na(mod\;L) \]

\[ma-na\equiv y-x(mod\;L) \]

\[(m-n)a\equiv y-x(mod\;L) \]

\(m,n,x,y\)都是已知常量，接下来我们就可以愉快套板子了

值得注意的是，\(m-n\)可能是一个负数,这时便需交换两只青蛙的值

P1292 倒酒

说实话，我觉得这题至少得评绿，楼上一板子题还是绿呢......

总而言之，这道题的思想还是很巧妙的

由\(P_{a}\)最小这一限制可知在a不满的时候就把a里面的酒倒出来是一种 傻逼透顶 没有价值（无法使答案最小，却会使\(P_{a}\)白白增大）的行为

又因为\(P_{b}\)也要尽量最小，所以结束是b酒杯中一定是空的。

综上，我们可以写出下面的式子

\[P_{b}\times b-P_{a}\times a=ans \]

若要让\(ans\)最小，则\(ans=gcd(P_{a},P_{b})\)

我们让\(P_{a},P_{b}\)同除于\(g\)，此时\(P_{a},P_{b}\)互质

接下来，我们就可以写出

\[P_{b}\times b-P_{a}\times a=gcd(P_{a},P_{b}) \]

带入扩展欧几里得算法就可求解

注意，不能直接求\(P_{a}\)的最小整数解，然后算出\(P_{b}\)，这样算出来的\(P_{b}\)可能是负数，此时我们需要不断给调整\(P_{a}\)来使\(P_{b}\)为正数

P3811 【模板】乘法逆元

此题参照我的另一篇题解

P2054 P2054 [AHOI2005]洗牌洗牌

可以看出，一张牌在被洗过一次后，它的位置就从\(p\)变成了\(2p\;mod\;(n+1)\)

假设一张牌p在移动m此后到达了位置x

\[2^{m}p\;\equiv x(mod\;n+1) \]

\(m,n,x\)均为已知量,代入同余方程就可得出m值

P2158 [SDOI2008] 仪仗队

一眼看出，这题要求的实际上是在\(1<=x,y<=n\)中，有多少组gcd(x,y)=1,即\(\phi(x)\)的和。用一个线性求欧拉函数即可

注意，最后的结果应\(\times 2+1\),因为gcd(x,y)和gcd(y,x)不同，并且(2,2)被忽略了

剩下来两道题明天再更新