CINTA作业三：同余、模指数、费尔马小定理、欧拉定理

1、实现求乘法逆元的函数，给定a和m，求a模m的乘法逆元，无解时请给出无解提示，并且只返回正整数。进而给出求解同余方程（ax = b mod m）的函数，即给定a，b，m，输出满足方程的x，无解给出无解提示。

int mul_i(int a, int b)
{
	int r1 = 1;
	int r2 = 0;
	int s1 = 0;
	int s2 = 1;
	while (b)
	{
		int mod1 = a % b;
		int div1 = a / b;
		a = b;
		b = mod1;

		int temp_r1 = r1;
		int temp_s1 = s1;
		r1 = r2;
		s1 = s2;

		r2 = temp_r1 - r1 * div1;
		s2 = temp_s1 - s1 * div1;
	}

	if (r1 >= b)
	{
		cout << "无解" << endl;
		return -1;
	}

	return r1;
}

int congruence(int a, int b, int m)
{
	int x = 1;
	if (mul_i(a, m) == -1)
	{
		cout << "无解" << endl;
		return -1;
	}
	else
	{
		x = b * mul_i(a, m);
		return x;
	}
}

2、实现模指数运算的函数，给定x、y和m，求x的y次方模m。

int mod_exp(int x, int y, int p)
{
	int res = 1;
	while (y > 0)
	{
		if ((y & 1) == 1) res = (res * x) % p;
		y = y / 2;
		x = (x * x) % p;
	}
	return res;
}

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

5 2020 m o d 23 = 5 ( 23 − 1 ) ∗ 91 + 18 m o d 23 = 5 18 m o d 23 = 6 5^{2020} mod 23 = 5^{(23-1)*91+18} mod 23 = 5^{18} mod 23 = 6 52020mod23=5(23−1)∗91+18mod23=518mod23=6

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

ϕ ( 55 ) = 40 ϕ (55)=40 ϕ(55)=40
2 100000 m o d 55 = 2 40 ∗ 2500 m o d 55 = 1 2^{100000} mod 55 = 2^{40*2500} mod 55 = 1 2100000mod55=240∗2500mod55=1

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

7 1000 7^{1000} 71000最后两位数与求 7 1000 m o d 100 7^{1000}mod100 71000mod100相同
ϕ ( 100 ) = 40 ϕ (100)=40 ϕ(100)=40
7 1000 m o d 100 = 7 40 ∗ 25 m o d 100 = 1 7^{1000}mod100 = 7^{40*25}mod100 = 1 71000mod100=740∗25mod100=1
最后两位数为：01