摘要
Title: 1299. 五指山
Tag: 线性同余方程、exgcd
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1299. 五指山

• 题意

  大圣在佛祖的手掌中。
  我们假设佛祖的手掌是一个圆圈，圆圈的长为 n，逆时针记为：0,1,2,…,n−1，而大圣每次飞的距离为 d。
  现在大圣所在的位置记为 x，而大圣想去的地方在 y。
  要你告诉大圣至少要飞多少次才能到达目的地。
  注意：孙悟空的筋斗云只沿着逆时针方向翻。

• 思路

  完整推导过程！(其中d代表下面代码的D)
  

  其中要注意最后求最小解，做完$exgcd$后三步走

  • 先判断是否有解，也就是等式右边是否能整除$d$
  • 再将结果放大
  • 最后推出通解公式，然后除余后面的数即可

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-04-01 16:43:26
  FilePath: \ACM\Acwing\1299.py
  LastEditTime: 2022-04-01 16:43:27
  '''
  
  
  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())):
      n, D, X, Y = map(int, input().split())
      x, y = 0, 0
      d = exgcd(D, n)
      if (Y - X) % d == 0:
          x *= (Y - X) // d #放大结果
          n //= d #处理除余的数
          print(x % n)
      else:
          print("Impossible")