CINTA hw2-526互联

1、写一个模指数运算函数Mod_Exp，输入a、b和m，输出a^b mod m，即a的b次方模m。

点击查看代码

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

// 模运算函数
int Mod(int num,int m) 
{
    return (num%m+m)%m;
}

// 平方并求模
int SquareMod(int a,int m) 
{
    a = (a*a)%m;
    return Mod(a,m);
}

// 右移除首位
string RShift(string s) 
{
    return s.substr(1);
}

// 快速幂取模
int ModExp(int a, int b, int m) 
{
    int res = 1;
    while (b!= 0) 
	{
        if (b&1) 
		{
            res = Mod(res*a,m);
        }
        a = SquareMod(a,m);
        b >>= 1;
    }
    return res;
}

int main() 
{
    int a, b, m;

    cout << "Enter a,b and m: ";
    cin >> a >> b >> m;

    int result = ModExp(a,b,m);
    cout << "Result: " << result << endl;
	system("pause");
    return 0;
}

运行结果

2、写一个求乘法逆元的函数Mul_Inverse，输入a和m，求a模m的乘法逆元。提示，要求只输出正整数。

点击查看代码

#include <iostream>
using namespace std;

int egcd(int a, int b, int& x, int& y) 
{

	if(b==0) 
		{
			x=1;
			y=0;
			return a;
		}

	int x1,y1;
	int g=egcd(b,a%b,x1,y1);

	x = y1;
	y = x1-(a/b)*y1;

	return g;
}
int Mul_Inverse(int a,int m) 
{
	//egcd递归计算乘法逆元 
	int x,y;
	int g = egcd(a,m,x,y);
  
	//若a和m不互质,则逆元不存在
	if(g!=1) return -1; 
  
	//使x为正整数
	int res=(x%m+m)%m;

	return res;
}

int main() 
{
	int a, m;
	cin >> a >> m;

	int result = Mul_Inverse(a, m);

	if(result == -1) {
		cout << "无乘法逆元";
  }
	else {
		cout << "乘法逆元为：" << result<<endl; 
  }
	system("pause");
	return 0;
}

运行结果