cinta-HW2

十月 17, 2023 549

编程题

1
2
3
4
5
6
7
8
9
10
11
int Mod_exp(int a,int b,int m=2147483647)//出于个人恶趣味把m初始化了，这样就能当pow用了
{
    int ans=1;
    if(a>m) a%=m;
	for(int i=0;i<b;i++){
		ans*=a;
		ans%=m;
	}
    return ans;
}
//模指数运算函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int Mul_Inverse(int a,int m)
{
	int ans;
	int r1=1,r2=0,s1=0,s2=1,q,r,s,a0=a,m0=m;
	while(m){
		q=a/m;
		int temp=a;
		a=m;
		m=temp%m;
		r=r1;
		r1=r2;
		r2=r-q*r2;
		s=s1;
		s1=s2;
		s2=s-q*s2;
	}
	if(a==1){
		while(r1<0) r1+=m0;
		ans=r1;
		}
	else ans=-1;
	return ans;
}
//求a模m的乘法逆元