回分類題庫
h052: D.輾轉難眠
關鍵字: NPSC 2008 高中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 23 Times / 21 Users | Submit : 33 Times / 23 Users | Accepted rate : 91%
題目加入時間 : 2011-11-10 10:46

Content: 简体中文

在火山高校中,數學老師魔方陣不滿學生的素質低落,於是出了一堆數學作業要大家回去寫,沒有寫出來的就開除學籍。大家都嚇了一跳,尤其是功課一向不怎麼好的金英俊。不過在當他們看到題目的標題就笑了出來,因為題目就是連國小生都會求的最大公因數問題!可是就在他們看到了題目的數字以後,大家的下巴就掉了下來。題目中的數字都是天文數字,想必今天晚上是必要「輾轉」難眠的算出答案了。身為金英俊好友的你可否幫他寫個程式處理這個問題呢?

首先在經過詳細觀察過題目之後你發現了以下幾個特性:

  1. 每一題的題目都是下面的樣子
    Gcd(am – bm, an –bn) 除以某個數 p 的餘數
  2. 0 < b < a <=1000, 1< m < n<=200, 1 < p <= 10000
  3. a 和 b 都互質

Input:

輸入檔中的每一行就包含一筆測試資料。每一行包含5 個整數用空白隔開,分別代表a, b, m, n, p。

Output:

對於每一組資料輸出一行 Gcd(am – bm, an –bn) 除以 p 的餘數。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
5 4 3 6 1000
37 17 50 20 2
889 73 2 34 8115

Sample Output :

61
0
5952

Hint :

Author :

NPSC 2008 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum