基礎題 Q-2-13 無理數的快速冪

題目連結：d024. Q_2_13 無理數的快速冪 (108高中全國賽, simplifed) – JMJudge

實做好無理數的乘法後就簡單了

#include<bits/stdc++.h>
using namespace std;

const int p=1000000009;
struct number{
    long long x,y;
};
number operator*(number a,number b){
    number c;
    c.x=((a.x*b.x%p)+(2*a.y*b.y%p))%p;
    c.y=((a.x*b.y%p)+(a.y*b.x%p))%p;
    return c;
}

number powerNum(number x,int n){
    if(n==1) return x;
    if(n&1) return x*powerNum(x,n-1);
    number t=powerNum(x,n/2);
    return t*t;
}

int main(){
    int n;
    number a;
    cin>>a.x>>a.y>>n;
    number ans=powerNum(a,n);
    cout<<ans.x<<" "<<ans.y;
    return 0;
}