Luogu P1082 同余方程

2020年3月25日 · 14 views · 

直达链接:Luogu P1082

经典的同余方程模板题。详见同余方程算法解析

直接上代码:

#include<iostream>
using namespace std;

void exgcd(int a, int b, int& x, int& y)
{
	int a1 = 0, b1 = 1, a2 = 1, b2 = 0;
	while (a%b!=0)
	{
		int k = a / b;
		x = a2 - k*a1;
		y = b2 - k * b1;
		a2 = a1, a1 = x, b2 = b1, b1 = y;
		int r = a % b;
		a = b;
		b = r;
	}
}

int main()
{
	int a, m, x, y;
	cin >> a >> m;
	exgcd(a, m, x, y);
	while (x > 0)
		x -= m;
	while (x <= 0)
		x += m;
	cout << x << endl;
}
返回

Steven's Website Copyright © 2020 Steven
Powerd by Wordpress & Theme by Steven
粤ICP备20028373号