1.cpp

来自「任用户随意的输入数值」· C++ 代码 · 共 66 行

#include <stdio.h>
#include <stdlib.h>
int mod_invese(int d,int n) 
{
	int a,b,q,r,u=0,v=1,t;
	a=n;
	b=(d>=0)?(d%n):-(d%n);
	
	while (b!=0)
	{

         q=(int)a/b;
	     r=a-b*q;
	     a=b;
	     b=r;
	     t=v;
	     v=u-q*v;
	     u=t;
	}
if(a!=1)
 return(-a);
return((u<0)?u+n:u);
}
int mod_power(int a,int k,int n)
{
	int x,y,t;
	y=a;
	t=k;
	if(t<0)
	{
		y=mod_invese(y,n);
		if(y<0) 
			return 0;
		t=-t;
	}
	x=1;
	if(t==0) 
		return 1;
	while(t>1)
	{
		if(t&0x00000001) x=(x*y)%n;
		y=(y*y)%n;
		t>>=1;
	}
	x=(x*y)%n;
	return (x);
}

		

void main()
{
	int n,d,a,k,m,z;
    printf("请输入模数n和d的值：\n");
	scanf("%d %d",&n,&d);
	m=mod_invese(d,n);
	printf("所求结果为：%d\n",m);
	printf("请输入要进行模幂运算的模数n、底数a、指数k的值：\n");
	scanf("%d %d %d",&n,&a,&k);
	z=mod_power(a,k,n);
    printf("所求结果为：%d\n",z);
	
}