中南大学2012暑期集训中期检测训练赛-求逆元

中南大学2012暑期集训中期检测训练赛-求逆元
强烈推介IDEA2020.2破解激活,IntelliJ IDEA 注册码,2020.2 IDEA 激活码

Problem A: 求逆元

Time Limit: 1 Sec  
Memory Limit: 2 MB


SUBMIT: 232  
Solved: 77


[SUBMIT]
[STATUS]

Description

给定正整数x,y,求最小的正整数z使得x*z mod y = 1。

Input

多组数据,每行两个整数x,y 空格隔开。2 <= x, y < 10^6。

Output

输出所求的数,如果小于y的数中不存在这样的数,输出No。

Sample Input

2 3
6 11

Sample Output

2
2

HINT

 

思路:原方程x*z mod y = 1可转移为:x*z-y*b=1,明显的扩展欧几里德,直接套模板。

 

#include<stdio.h> 
int exgcd(int a,int b,int &x,int &y)  
{     
	int i,j;     
	if(b==0)     
	{         
		x=1;         
		y=0;         
		return a;     
	}     
	i=exgcd(b,a%b,x,y);     
	j=x;     
	x=y;     
	y=j-a/b*y;     
	return i; 
} 
int main() 
{     
	int a,b,x,y,r;     
	while(scanf("%d %d",&a,&b)!=EOF)     
	{         
		r=exgcd(a,b,x,y);         
		if(r==1)         
		{             
			while(x<0)             
			{                 
				x+=b;                 
				y-=a;             
			}             
			printf("%d\n",x);        
		}
		else            
			printf("No\n");     
	}     
	return 0; 
}

 

本文来源程序员囧辉,由javajgs_com转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/8844

发表评论