摘要
Title: 1301. C 循环
Tag: 线性同余方程、exgcd
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1301. C 循环

• 题意

  对于 C 语言的循环语句，形如：
  for (variable = A; variable != B; variable += C)
  statement;
  请问在 k 位存储系统中循环几次才会结束。
  若在有限次内结束，则输出循环次数。否则输出死循环。

• 思路

  $k$位系统的意思为，每个数都模上$2^k$
  也就是

  $$(a + xc) mod 2 ^k = b$$

  求最小的x即可

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-04-01 19:52:10
  FilePath: \ACM\Acwing\1301.py
  LastEditTime: 2022-04-01 19:52:11
  '''
  
  
  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
  
  
  while True:
      a, b, c, k = map(int, input().split())
      if k == 0:
          break
      x, y = 0, 0
      d = exgcd(c, 2**k)
      if (b - a) % d == 0:
          x *= (b - a) // d
          n = 2**k // d
          print(x % n)
      else:
          print("FOREVER")