题目描述

基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题 收藏 关注
给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。
Input
输入2个数M, N中间用空格分隔（1 <= M < N <= 10^9)
Output
输出一个数K，满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。
Input示例
2 3
Output示例
2

解题思想

/*
 应为M，N互质，K * M % N = 1
 所以M*k + N(-x)=1
 所以一看就是扩展欧几里得定理
*/

代码

import java.util.Scanner;
public class Main{
    static int x, y;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        exgcd(m,n,x,y);
        while(x < 0){
            x += n;
        }
        System.out.println(x);
    }
    public static void exgcd(int a, int b, int a1, int b1){
        if(b ==0){
            x = 1;
            y = 0;
            return;
        }else{
            exgcd(b, a%b, x, y);
            int t = x;
            x = y;
            y =t - a/b*y;
        }
    }
}