給定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
} } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/93562.html
標籤：其他
上一篇：擴展歐幾里得（模板）
下一篇：885.求組合數 I（模板）