题目描述

blablabla

样例

blablabla

Java 代码

import java.util.*;

public class Main{
    static int x , y;

     public  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 sc = new Scanner(System.in);
        int n = sc.nextInt();

        while(n-- > 0)
        {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int m = sc.nextInt();
            int d = exgcd(a, m);
            if(b % d > 0 ) System.out.println("impossible");
            else System.out.println((long) x * (b / d) % m);
        }
    }
}