boj 591

蛋疼的晚上打开一道题boj 591，发现就是辗转相除法，求系数。。。然后先是输出“Not Exist”打错为“No Exist”，后来又少写return 0;狗血。。。。。。

#include<iostream>
using namespace std;

int judge(int max,int min,int &first,int &second)//辗转相除 max*first+min*second = 1
{
	if(max%min==0)
		return 0;
	if(max%min==1)
	{
		int tmp = max/min;
		first = 1;
		second = 0-tmp;
		return 1;
	}
	if(judge(min,max%min,first,second))
	{
		int tmp = second;
		second = first-(max/min)*second;
		first = tmp;
	return 1;
	}
	return 0;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int a,m;
		scanf("%d%d",&a,&m);
		if(a==1||m==1)
		{
			printf("1\n");
			continue;
		}
		int first ,second;
		if(!judge(m,a,first,second))
			printf("Not Exist\n");
		else
			printf("%d\n",(second+m)%m);
	}
}

 

评论

1 楼 zsybupt 2013-02-07