摘要
Title: 878. 线性同余方程
Tag: exgcd
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

878. 线性同余方程

• 题意

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

• 思路

  定理：对于方程式$ax + by = d$，$d | gcd(a, b)$是方程一定有整数解的充分必要条件
  

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-11 15:18:46
  FilePath: \ACM\Acwing\878.py
  LastEditTime: 2022-03-11 15:18:47
  '''
  
  
  def exgcd(a, b):
      global x, y
      if b == 0:
          x, y = 1, 0
          return a
  
      d = exgcd(b, a % b)
      x, y = y, x
      y -= (a // b) * x
      return d
  
  
  for _ in range(int(input())):
      a, b, m = map(int, input().split())
      x, y = 0, 0
      d = exgcd(a, m)
      if b % d == 0:
          print(x * b // d % m)
      else:
          print("impossible")