竹園論壇

標題: [任務]JOG 解題的第36題 [打印本頁]

作者: 零人桐 時間: 2014-8-5 10:54
標題: [任務]JOG 解題的第36題
任務的第36題
寫出來是WA
程式碼如下
幫忙抓一下BUG
Thank you!

JOG 36 題

網址: http://toj.tfcis.org/oj/chal/5458/

程式碼

#include<iostream>
#include <cmath>
using namespace std;
int main()
{
      int a,b,c,x;
      cin>>a>>b>>c;
      if( a>=0 && a<pow( 2,31 ) &&  b>=0 && b<pow( 2,63 ) && c>=1 && c<=9439 )
      {
            x=pow( a,b );
            cout<<x % c<<endl;
      }
      return 0;
}

作者: domen111 時間: 2014-8-5 11:31
這題雖然屬於簡單問題集，但沒你想的那麼簡單喔! (其實簡單問題集的題目也都不是非常簡單)
這題你必須要學會模運算和快速冪，如果都會了就很簡單了

你可以看看測資範圍，(2^31)的(2^63)次方int或long long怎麼可能存的下

作者: 零人桐 時間: 2014-8-5 11:56
ㄎㄎ我打錯了
是TOJ

作者: 零人桐 時間: 2014-8-6 21:40

[C++] 純文本查看 復制代碼

#include<iostream>

#include <cmath>

using namespace std;

int main()

{

        int a,b,c,x;

        cin>>a>>b>>c;

        if( a>=0 && a<pow( 2,31 ) &&  b>=0 && b<pow( 2,63 ) && c>=1 && c<=9439 )

        {

                x=pow( a,b );

                cout<<x % c<<endl;

        }

        return 0;

}

作者: 零人桐 時間: 2014-8-6 21:41
那要怎麼存?

作者: 零人桐 時間: 2014-8-6 21:41
(既然存不下)

作者: domen111 時間: 2014-8-6 21:46
模運算就用用到一些mod(%)的原理，一邊算一邊mod就不用存那麼多資料了
不過既然要一邊算一邊mod那就必須要自己寫一個pow，pow如果只用一個for迴圈下去算會執行很久，得到一個TLE(Time Limit Exceed)，所以你必須要寫個function去遞迴計算。

作者: Sylveon 時間: 2014-8-6 22:16
先了解取MOD的性質 (WIKI)
這裡的%是C++的取餘數
加減法原則
( A ± B ) % C = A % C ± B % C

乘法原則
( A * B ) % C =( A % C ) * ( B % C )

(除法原則不會別亂用)
AC % M = BC 且 ( M , C )=1，則 A % M = B

冪次
A[sup]B[/sup] % C = ( A % C )[sup]B[/sup]

(LATEX 線上編輯器)
快速冪：
[tex]%5Cfn_phv%20%5Clarge%20Fast%5C%20Exponentiation%5C%20Algorithms%5C%5C%20A%5E%7Bx%7D%20%3D%5C%5C%20%5Cbegin%7Bcases%7D%201%20%26%20%5Ctext%7B%20if%20%7D%20x%3D%200%5C%5C%20%28A%5E%7B%5Cfrac%7Bx%7D%7B2%7D%7D%29%5E%7B2%7D%20%26%20%5Ctext%7B%20if%20%7D%20x%20%5Cin%20Even%282%2C4%2C6%2C8...%29%5C%5C%20A%28A%5E%7B%5Cfrac%7Bx-1%7D%7B2%7D%7D%29%5E%7B2%7D%20%26%20%5Ctext%7B%20if%20%7D%20x%20%5Cin%20Odd%20%281%2C3%2C5%2C7...%29%20%5Cend%7Bcases%7D[/tex]

作者: 零人桐 時間: 2014-8-9 21:29
哦~
雖然不知道要怎麼用(是根本不懂)
但還是謝謝學長!

歡迎光臨竹園論壇 (http://forum.tfcis.org/)