Kurukshetra Athena 來自印度的數學程式競賽

上週從 Project Euler 傳來一個數學程式競賽的消息。
競賽的網址如下:
http://www.athena.kurukshetra.org.in/

這個競賽的題目都是數學相關問題，包含動態規劃、數論和許多領域，厲害的人也許能夠不依賴電腦就算出答案哩。雖然今年比賽已經結束了，有興趣的人還是可以去看看題目，並期待明年的比賽!

我今年沒有花很多時間，一周的時間內只完成了七題 :p
Score: 700 (完成七題)
Rank: 241

Question 6

There are 52735727364727372 students and 2889221271829121 teachers in a school . On children's day each teacher brings x toffees with him/her . All the toffees are collected and distributed equally to all the students . At the end it was found that there was exactly one toffee remaining .
What is the least possible value of x ?


我的想法
恩，這是很經典的一個問題。
首先我發現到分配之後只剩下一顆太妃糖，這表示老師的數目a和學生的數目b是互質的。接著把未知數 x 和 a,b 關聯起來，並且引入一個輔助變數 y 來表示每個學生所拿到的太妃糖數目，寫成數學形式是:
ax-by=1

接著我去查詢兩個互質的數有甚麼關連，發現了一個形式相似的公式: Bézout's identity，此公式說對於任意非零整數a和b，令其最大公因數為d，則存在x和y使得 ax+by=d。

要解出 x 和 y 可使用 Extended Euclidean algorithm，用 python 來寫的話只需要六行，而且還支援大數運算，真是相當輕鬆。

def extended_gcd(a,b):

  """Return x,y satisfy ax+by=gcd(a,b)"""
  if a % b == 0:
    return 0,1
  else:
    r = extended_gcd(b, a % b)
  return r[1], r[0] - (r[1] * (a / b))

找到 x, y 之後回到原來的問題。理論上符合 ax+by=d 的 (x,y) 有無限多組，此題目要求我們找的 x 為最小的正整數，剛好 extended_gcd 演算法得到的就是題目所要的。