再帰関数を使わないゲーム
ちょっとハマったのでまたやってみた。
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はちょいムズそう。