NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2008高中組決賽
 NPSC 2008 高中組 決賽 D.輾轉難眠

作者 主題: NPSC 2008 高中組 決賽 D.輾轉難眠  (閱讀 1810 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 231
    • 檢視個人資料
NPSC 2008 高中組 決賽 D.輾轉難眠
« 於: 十一月 30, 2009, 01:50:04 pm »

NPSC 2008 高中組 決賽 D.輾轉難眠

感謝 su_horng 提供解題提示。

說明:給你五個整數 a、b、m、n、p,請你求出 a^m-b^m 和 a^n-b^n 的最大公因數的值再除以 p 的餘數,即 GCD(a^m-b^m, a^n-b^n)%p 的值。

解法:數學解,GCD(a^m - b^m, a^n - b^n) % p = [ a^GCD(m,n) - b^GCD(m,n) ] %p ,利用此一公式,用迴圈求解即可。其中 a^k 的值可能超過 int 或 long long int 的範圍,可以一邊計算 a 的次方,一邊將乘起來的結果除以 p 取餘數,結果是一樣的。至於為什麼是這個公式,請知道的網友幫忙補充。

參考程式:(By sagit)

代碼: [選擇]
// NPSC 2008 高中組決賽
// 題目 D - 輾轉難眠
// By sagit at TCGS
#include <cstdlib>
#include <iostream>

using namespace std;

int GCD(int m, int n)                   // 求最大公因數
{
    int k;
    while (n!=0)                        // 輾轉相除法
    {
          k=m%n;
          m=n;
          n=k;
    }
    return m;
}

int Pow(int a, int n, int p)            // 求 (a^n)%p 的值
{
    int i, t;
    for (i=0, t=1; i<n; i++)
        t=(t*a)%p;
    return t;
}

int main()
{
    freopen("pd.in", "rt", stdin);
    freopen("pd.out", "w+t", stdout);
    ios_base::sync_with_stdio(false);
    int a, b, m, n, p, g, t;
    while (1)
    {
        cin >> a >> b >> m >> n >> p;
        if (cin.fail()) break;
        if (a<b) { t=a; a=b; b=t; }     // 將 a 調整成較大的那個數
        g=GCD(m, n);
        a=Pow(a, g, p);
        b=Pow(b, g, p);
        cout << (p+a-b)%p << endl;
    }
//    system("PAUSE");
    return 0;
}
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 231
    • 檢視個人資料
su_horng 提供的數學推演過程
« 回覆 #1 於: 十一月 30, 2009, 01:51:13 pm »

su_horng 提供的數學推演過程

peter50216學長提供的算式:

( a^m - b^m , a^n - b^n )
=( a^m - b^m , a^n - b^n - (a^m - b^m)*a^(n-m) )
=( a^m - b^m , - b^n + b^m*a^(n-m) )
=( a^m - b^m , b^m*a^(n-m) - b^(n-m)*b^m )
=( a^m - b^m , b^m*(a^(n-m) - b^(n-m)) )
=( a^m - b^m , a^(n-m) - b^(n-m) )
= ... = a^(n,m) - b^(n,m)
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2008高中組決賽
 NPSC 2008 高中組 決賽 D.輾轉難眠