线性同余方程(同余+扩展欧几里得模板)

给定n组数据ai,bi,mi,对于每组数求出一个xi,使其满足ai∗xi≡bi(mod mi),如果无解则输出impossible。

输入格式

第一行包含整数n。

接下来n行,每行包含一组数据ai,bi,mi。

输出格式

输出共n行,每组数据输出一个整数表示一个满足条件的xi,如果无解则输出impossible。

每组数据结果占一行,结果可能不唯一,输出任意一个满足条件的结果均可。

输出答案必须在int范围之内。

思路:

线性同余方程(同余+扩展欧几里得模板)

 代码:

import java.util.Scanner;

public class Main{
        static int x,y;
        static int exgcd(int a,int b){
                if(b==0){
                        x=1;
                        y=0;
                        return a;
                }
                int d=exgcd(b,a%b);
                int t=x;
                x=y;
                y=t-a/b*y;
                return d;
        }
         public static void main(String[] args) {
                 Scanner scan=new Scanner(System.in);
                 int t=scan.nextInt();
                 while(t-->0){
                         int a=scan.nextInt();
                         int b=scan.nextInt();
                         int m=scan.nextInt();
                         int d=exgcd(a,m);
                         if(b%d!=0) System.out.println("impossible");
                         else System.out.println((long)x*(b/d)%m);//注意超int,用long
} } }

 

上一篇:【Redis】几个高级命令


下一篇:算法练习(1)