嗯，作为$NOIP2012tg \; Day2T1$还是比较合适的，只不过题面。。。。(~~可能是出题人yy不出来了~~)

题目描述

求关于$x$的方程$ax \equiv 1(mod \;b)$的最小正整数解。

输入输出格式

输入格式

一行，包含两个正整数$a,b$。

输出格式

一个正整数 $x_0$ ，即最小正整数解。输入数据保证一定有解。

INPUT & OUTPUT’s examples

Input’s eg #1

3 10

Output’s eg #1

说明

对于 40%的数据，$2 \leq b \leq 10^3$

对于 60%的数据，$2 \leq b \leq 5 \times 10^7$

对于 100%的数据，$2 \leq a, b \leq 2 \times 10^9$。

分析

题面已经裸到一句话了。。。。

我们把原始题面魔改一下：

$$ax \equiv 1(mod\; b)$$

因为我们最后$mod\;b$，所以在同余式左边加一个$b \times y$不会影响结果。

$$ax+by \equiv 1(mod\;b)$$

但是我们的扩展欧几里得算法是用来求解以下算式的：

$$ax+by \equiv gcd(a,b)$$

所以~~显然可以看出~~得出结论：$gcd(a,b)=1$，即$a,b$互质。

由欧几里得算法可得：

$$gcd(a,b)=gcd(b,a\%b)$$

我们假设有另一组解$x_2,y_2$存在，

那么:

$$b \times x_2+(a \% b)\times y_2 \equiv ax+by \equiv 1$$

魔改：
因为，
$$a \% b = a - \lfloor \frac{a}{b} \rfloor \times b$$

所以，

$$bx_2+(\frac{(a-b)a}{b})y_2 \equiv ax+by$$

乘法分配律：

$$bx_2+ax_2-y_2(\frac{ab}{b}) \equiv ax+by$$

继续化简：

$$ay_2+b(x_2-y_2(\frac{a}{b})) \equiv ax+by$$

类比之前的式子：

$$x=y_2,y=x_2-y_2(\frac{a}{b})$$

直接一层层递归即可

代码

/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
using namespace std;
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*its=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==its)
            its=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==its)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
using namespace FastIO;
/* definitions */
long long a,b,x,y;
/* functions */
inline long long ex_gcd(long long a,long long b,long long &x,long long &y){
    if(!b){x=1;y=0; return a;}
    long long k=ex_gcd(b,a%b,y,x);
    y-=a/b*x;
    return k;
}
inline long long mod(long long a,long long b,long long p){
    return (a%p+b)%p;
}
int main(int argc,char *argv[]){
    scanf("%lld%lld",&a,&b);
    ex_gcd(a,b,x,y);
    printf("%lld\n",mod(x,b,b));
    return 0;
}

洛谷P1082$\lceil$NOIP2012提高组$\rfloor$题解