题解 | 同余方程-NOIP2012提高组复赛A题

输入描述:

显然这是一道裸的数论题目。

对于一个临考试抱佛脚的蒟蒻，数论的东西还是知道的很少...

就简单说说我做这个题目的时候，在几个地方栽下的跟头，希望让以后做这道题目的同学引以为戒。

PS：这道题我选择使用扩展欧几里得解决，百度了许多博客，觉得这篇文章讲的还是比较简明易懂的，大家可以点击一下->

（在证明的时候掏出纸和笔，这是一个好习惯！）

-第一，题目中让我们求的是最小正整数解，而我们使用的算法最后得出的结果可能为负数，这就需要我们在最后得出结果时，加一个整数再去模b，即输出结果时用以下语句：cout<<(x+b)%b;这样我们就得到一个最小正整数解了！

-第二，问题的转化。

可能对我这种数论渣渣，理解楼下题解的话花了不少时间...在这里为同样和我蒻的同学说明一下。

首先解释一下平时在数学课本上不出现的符号≡，同余符号，含义为两个整数a，b，若它们除以整数m所得的余数相等，则称a，b对于模m同余，记作a≡b(mod m)。

那么，同余方程ax ≡ 1 (mod b)，如果转化为我们通俗易懂的语言就是->求满足ax%b=1，1%b=1最小正整数解。

那么接下来就可以使用扩展欧几里得解决了。

-第三，楼下题解中，很多代码都是这种形式

int exgcd(int a,int b,int &x,int &y)

而天真的我没有加上“&”符号，这就导致了我的程序Wa掉了...

int exgcd(int a,int b,int x,int y)

翻阅了评论区，看到一个dalao HanayoOI告诉我们说：扩展欧几里德需要修改x,y变量本身来实现。

而不加“&”符号，那么在exgcd执行完后x和y不会被修改。

根据楼下大神的建议，我们可以把x,y设置为全局变量，这样就可以避免一些麻烦。

那么，我们就可以得到如下代码：

#include <iostream>  
#include <cstdio> 
using namespace std;
int a,b,x,y,k;
void exgcd(int a,int b)
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b);
    k=x;
    x=y;
    y=k-a/b*y;
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>a>>b;
    exgcd(a,b);
    cout<<(x+b)%b;
}