読者です 読者をやめる 読者になる 読者になる

再帰関数を使わないゲーム

programming

ちょっとハマったのでまたやってみた。
hogeのpiyo乗をO(log piyo)で求めるやつ。
簡単だと思ったら、案の定簡単だった。
再帰verとちょっとだけ方針が違う。

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
using namespace std;
typedef long long ll;

const int mod = 1000000007;

// recursive ver
int pow1(int a, int b){
    if(b == 0) return 1;
    ll x = pow1(a,b>>1);
    return (x*x%mod)*((b&1)?a:1)%mod;
}
//

// not recursive ver
int pow2(int a, int b){
    ll x = a, res = 1;
    
    while(b){
        if(b&1) res = res*x%mod;
        x = x*x%mod;
        b >>= 1;
    }
    
    return res;
}
//

int main(){
    srand((unsigned)time(NULL));
    
    int n, a, b, ans1, ans2;
    bool bl = true;
    scanf("%d",&n);
    
    rep(i,n){
        a = rand()%mod; b = rand()%mod;
        
        ans1 = pow1(a,b);
        ans2 = pow2(a,b);
        
        printf("Case %04d: %10d^%10d , pow1 - %10d , pow2 - %10d : %s\n",i,a,b,ans1,ans2,ans1==ans2?"Correct":"Wrong");
        if(ans1 != ans2) bl = false;
    }
    
    puts(bl?"YES":"NO");
    
    return 0;
}

多分gcdは簡単で、extgcdはちょいムズそう。