Dark`Kris

Private blog

I'm spark , hope you fire


NOIp2012TG/Luogu P1082 同余方程 解题报告

这是一道数论题,是扩展欧几里得算法的裸题 博主为了让自己记住这个算法,特地来写一篇博文

下面来看看一下题:

题目描述

求关于 x 的同余方程 的最小正整数解。

输入输出格式

输入格式: 输入只有一行,包含两个正整数 a, b,用一个空格隔开。

输出格式: 输出只有一行,包含一个正整数 x0,即最小正整数解。输入数据保证一定有解。

输入输出样例

输入样例#1: 3 10 输出样例#1: 7

说明

【数据范围】

对于 40%的数据,2 ≤b≤ 1,000;

对于 60%的数据,2 ≤b≤ 50,000,000;

对于 100%的数据,2 ≤a, b≤ 2,000,000,000。

NOIP 2012 提高组 第二天 第一题


解题思路

扩展欧几里得算法

分析: 可以通过移项变为: . 然后再次变为 。即: 。 所以用扩展欧几里德方法解就可以了。

下面是C++代码:

#include <iostream>
#include <cstdio>
using namespace std;
long long x,y,a,b,ans;
long long gcd(long long a,long long b)//扩展欧几里得算法
{
	long long t,ret;
	if(b==0)//欧几里得算法
	{
		x=1;
		y=0;
		return a;
	}
	ret=gcd(b,a%b);
	t=y;//扩展欧几里得
	y=x-(a/b)*y;
	x=t;
	return ret;
}
int main()
{
	cin>>a>>b;
	ans=gcd(a,b);
	while(x>b)x-=b; //输出最小正整数解
	while(x<0)x+=b;
	cout<<x<<endl;
	return 0;
}

写给自己:如果无法理解,建议背过代码

感谢惠读

Tips

Cancel

Thanks a lot,I will be better!

scan possible
scan possible
Scan and give tips as you wish

OpenAlipayScan it and give tips as you wish

Wait a minute,Loading