NOIP 2012-同余方程

[mathjax]

题目链接 :CH3301

用拓展欧几里得算法求出一组特解\(x_0,y_0\),则\(x_0\)就是原方程的一个解,通解为所有模\(b\)与\(x_0\)同余的整数.题目要求是最小正整数解,可通过取模操作把解的范围移动到\([1,b)\)之间,\([1,b)\)之间的就是最小正整数解.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int exgcd(int a,int b,int &x,int &y){
  if(b==0) {x=1;y=0;return a;}
  int d=exgcd(b,a%b,x,y);
  int z=x;x=y;y=z-y*(a/b);
  return d;
}

int main(){
  int a,b;
  cin>>a>>b;
  int x,y;
  exgcd(a,b,x,y);
  cout<<(x%b+b)%b<<endl; //注意x可能是负数
  return 0;
}