[任務]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

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

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

零人桐

ㄎㄎ我打錯了
是TOJ

零人桐

[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;
}

零人桐

那要怎麼存?

零人桐

(既然存不下)

domen111

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

Sylveon

先了解取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]

零人桐

哦~
雖然不知道要怎麼用(是根本不懂)
但還是謝謝學長!