P101 求root(N, k)

原本想这样模拟过程但是这样太复杂。需要思考别的方法~

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

bool Judge(vector<int> n, int k){
    int len = n.size();
    if(len > 2){
        return false;
    }else if(len == 2){
        if()
    }
}

vector<int> n root(vector<int> n, int k){
    int n1 = 0;
    int len = n.size();
    if(len > 2 ){

        return root(n1, k);
    }else if(len == 2){
        if()
    }
}

vector<int> getNum(int x){
    vector<int> ans;
    while(x != 0){
        ans.push_back(x % 10);
        x /= 10;
    }
    return ans;
}

vector<int> Multiply(vector<int> x, vector<int> y){
    int m = x.size(), n = y.size();
    vector<int> ans(m + n, 0);
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            ans[i+j] = x[i] * y[j];
        }
    }
    for(int i = 0; i < m + n + 2; i++){
        if(ans[i] >= 10){
            ans[i+1] += ans[i] / 10;
            ans[i] %= 10;
        }
    }
    return ans;
}

vector<int> FastExponentiation(vector<int> x, vector<int> y){

}

int main(){
    int x, y, k;
    while(cin >> x >> y >> k){
        vector<int> product, num1, num2;
        num1 = getNum(x);
        num2 = getNum(y);
        product = Multiply(num1, num2);

    }
}

通过的答案

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

//这里要用longlongint，只用int结果会出错，还不知道原因。
int func(long long int x, long long int y, int k){
    int ans = 1;
    while(y > 0){
        if(y % 2 ==1){
            ans = (ans * x) % k;
        }
        x = (x*x)%k;
        y /= 2;
    }
    return ans;
}

int main(){
    int x, y, k;
    while(cin >> x >> y >> k){
        int ans = func(x, y, k-1);//要注意模是k-1，而不是k
        if(ans == 0){
            cout << k-1 << endl;
        }else{
            cout << ans << endl;; 
        }
    }
    return 0;
}