TYVJ P2074 [NOIP2012T4]同余方程

背景noip2012-tg

描述

求关于 x的同余方程  ax ≡ 1(mod b) 的最小正整数解。

输入格式

输入文件 mod.in
输入只有一行,包含两个正整数a,b,用一个空格隔开。

输出格式

输出文件 为 modmod .out 。
输出只有一行,包含一个正整数,包含一个正整数 ,包含一个正整数 x0,即最小正整数解。 输入据保证一定有解。

测试样例1

输入

3 10

输出

7

备注对于 40% 的数据    2 ≤b≤1,000
对于 60% 的数据    2 ≤b≤50,000,000
对于 100%的数据    2 ≤a, b≤2,000,000,000 NOIP2012-TG

拓展欧几里得算法。。。。但是这个xy到底是什么鬼啊。。。。LYD你光给个函数为啥不好好讲讲啊。。。

#include <iostream>

using namespace std;
long long exgcd(long long a,long long b,long long &x,long long &y){
    if(b==0){x=1;return a;}
    long long d = exgcd(b,a%b,x,y);
    long long z=x;x=y;y=z-y*(a/b);
    return d;
}
int main()
{
    long long a,b,x=0,y=0;
    cin>>a>>b;
    exgcd(a,b,x,y);
    cout<<((x%b)+b)%b;
}

 

此条目发表在NOIP, TYVJ, 拓展欧几里得, 数论分类目录。将固定链接加入收藏夹。