CINTA作业3

#include 
using namespace std;

int x(int a,int b){
    int n;
    if (a != 0 && b != 0) {
        do {
            n = a % b;
            a = b;
            b = n;
        } while (n);
        return a;
    }
    else
        return -1;
    return 0;
}

int M(int a, int b) {
    int t;
    if (x(a, b) == 0&&x(a,b)==-1)
    {
        cout << "无解" << endl;
        return -1;
    }
    else
    {
        t = 1;
        while ((a * t) % b != 1)
            t++;
            return t;
    }
}
int main() {
    int a, m;
    cin >> a >> m;
    int x = M(a, m);
    cout << x;
}

2.

int mozhishu(int x, int y, int n) {
    int a = 1;
    if (y == 0)
        return 1;
        for (; y > 0; y /= 2)
        {
            a = (a * x) % n;
            x = (x * x) % n;
        }
        return a;
}

int main() {
    int x, y, m;
    cin >> x >> y >> m;
    x = mozhishu(x, y, m);
    cout << x;
    return 0;
}

3.设p = 23和a = 5，使用费尔马小定理计算a^{2020} mod p?

4.使用欧拉定理计算2^{100000} mod 55

φ(55)=40，即2^40mod55=1.2^100000mod55=2^40*2500mod55=1

5.手动计算7^{1000}的最后两个数位等于什么？