【C++】【数学】CINTA作业三

1、实现求乘法逆元的函数，给定a和m，求a模m的乘法逆元，无解时请给出无解提示，并且只返回正整数。 进而给出求解同余方程（ax = b mod m）的函数，即给定a，b，m，输出满足方程的x，无解给出无解提示。 2、实现模指数运算的函数，给定x、y和m，求x的y次方模m。 3、设p = 23和a = 5，使用费尔马小定理计算a^{2020} mod p? 4、使用欧拉定理计算2^{100000} mod 55。 5、手动计算7^{1000}的最后两个数位等于什么？

   代码很多，分量很足，写了一天，菜鸡一条。很糟心的是CSDN的博客，代码是不能折叠的。(找了半个多小时代码折叠，最后有个博客直说了，“CSDN的博客暂不支持”：Markdown中实现内容及代码块折叠操作)
   只能说这博客的内容编辑是挺混乱的，乱七八糟可以说是。“高亮”、“加粗”、“斜体”、“字体大小”之类的基本能用html标签代替，“空格”、“换行”、“字体颜色”只能用html标签实现。嘛，算了，谁没事去写博客啊。

代码

弄了一堆的文件，简述如下：
【GlobalSet.h】：声明了一堆要用的函数(模板是没法把定义扔进cpp文件的)
【GlobalSet.cpp】：完成GlobalSet.h里头声明的函数的定义(用了static变量防变量“外出”)
【Test1.cpp】：题目1的代码
【Test2.cpp】：题目2的代码
【Test3.cpp】：题目3的代码
【Test4.cpp】：题目4的代码
【Test5.cpp】：题目5的代码
【Main.cpp】：就main主函数而已，调用上面那几个Test.cpp文件写好的函数

//GlobalSet.h

#pragma once
#ifndef GLOBALSET_H
#define GLOBALSET_H

#include
using namespace std;
typedef unsigned int uint;

vector EGCD(int a, int b);//新写的EGCD。之前作业二写的EGCD弃用
uint Inverse_Multi(int a, uint m);//模m下a的乘法逆元（无解时返回0
uint Mod(int x, uint m);//求x%m
uint Pow(int x, int y, uint m);求x^y (mod m)。m=0时不取模
bool IsPrime(uint m);//判断是否为素数
uint PHI(uint m);//欧拉函数φ(m)

template//模板的定义和声明不能分离。(这个函数没什么实用，还浪费了不少时间编写。单纯就练习算法了(但还写的贼烂)
static int Search(vector& lst, T val) {//寻找成功时返回下标，失败则返回-1
	if (lst.empty())
		return -1;

	uint left = 0;
	uint right = lst.size() - 1;
	if (lst[left] > lst[right]) {
		left = right;
		right = 0;
	}
	struct {
		uint L : 1;//这位域感觉没啥用，算了就这样留着
		uint M : 1;
		uint R : 1;
		uint : 29;
	}flag{ 0 };

	while (true) {//二分法查找
		uint mid = (left + right) / 2;
		if (mid == left || mid == right)
			break;
		flag.L = lst[left] < val;
		flag.M = lst[mid] < val;
		flag.R = lst[right] < val;
		if ((flag.R == flag.M))
			right = mid;
		else
			left = mid;
	}
	if (lst[left] == val)
		return left;
	if(lst[right]==val)
		return right;
	return -1;
}

#endif

#include"GlobalSet.h"
#include

//Main.cpp



#include"GlobalSet.h"
void Test1();
void Test2();
void Test3();
void Test4();
void Test5();

int main() {
	Test1();
	Test2();
	Test3();
	Test4();
	Test5();

	return 0;
}

//Test1.cpp



#include"GlobalSet.h"

static vector SolveFunction_1(int a, int b, uint m) {//解决题1给出的方程题：Ax≡B (mod m)
	vector result;
	if (m > 0) {
		b=Mod(b, m);
		auto rst = EGCD(a, m);
		if (b % rst[2] == 0) {
			auto r = rst[0] * (b / rst[2]);
			auto step = m / rst[2];
			while (r < 0)
				r += step;
			r %= m;
			for (auto n = 0; n++ < rst[2]; r += step) {
				result.push_back(r);
			}
		}
	}
	return result;
}

void Test1_1() {
	int m = 12;
	vectortestNum{3,7,12,-5,29,39,-35};

	printf("【题目1.1(求乘法逆元)】n");
	for(auto p=testNum.begin();p!=testNum.end();++p)
		printf("ta=%-7d   m=%-7d   1/a=%-7dn", *p, m, Inverse_Multi(*p, m));

	printf("nn");
}

void Test1_2() {
	vector>testNum;//格式为[(a,b,m) , (a,b,m) , (a,b,m),...]
	testNum.push_back(vector{4, 8, 10});
	testNum.push_back(vector{5, 1, 12});
	testNum.push_back(vector{6,-3,15});
	testNum.push_back(vector{-7,7,9});
	testNum.push_back(vector{-5,-7,13});
	testNum.push_back(vector{6,5,12});
	testNum.push_back(vector{7,53,12});
	testNum.push_back(vector{-48,-37,5});

	printf("【题目1.2(求解同余方程Ax≡b(mod m))】n");
	for (auto p = testNum.begin(); p != testNum.end(); ++p) {
		auto rst = SolveFunction_1((*p)[0], (*p)[1], (*p)[2]);
		printf("%7dx≡%dt( mod %d )tx=",(*p)[0], (*p)[1], (*p)[2]);
		if (rst.empty())
			printf("* ");
		else {
			for (auto p = rst.begin(); p != rst.end(); ++p)
				printf("%d,", *p);
		}
		printf("b n");
	}
	printf("nn");
}

void Test1() {
	Test1_1();
	Test1_2();
}

//Test2.cpp



#include"GlobalSet.h"

void Test2() {
	vector>testNum;//格式为[(x,y,m) , (x,y,m) , (x,y,m),...]
	testNum.push_back(vector{-7, 5, 0});//模为0时不取模
	testNum.push_back(vector{-7, -5, 0});//不取模时负数幂所得结果为0
	testNum.push_back(vector{-7, 5, 10});//系统自带计算器，模式切换为科学计算可对运算结果进行检验
	testNum.push_back(vector{5, -3, 10});//负数幂需要求逆元，当逆元不存在时结果为0
	testNum.push_back(vector{9, -3, 10});//系统自带计算器对负数幂无法检验(主要是求不了逆元)
	testNum.push_back(vector{15, 23, 13});
	testNum.push_back(vector{-12, 63, 15});
	testNum.push_back(vector{-55, -47, 29});
	testNum.push_back(vector{-18, -19, 34});
	printf("【题目2(实现模指数运算)】n");
	for (auto p = testNum.begin(); p != testNum.end(); ++p) {
		printf("%7d ^ %-7d = %-12d( mod %d )n", (*p)[0], (*p)[1], Pow((*p)[0], (*p)[1], (*p)[2]), (*p)[2]);
	}

	testNum.clear();
	testNum.push_back(vector{5, 2020, 23});
	testNum.push_back(vector{43, 3548, 89});
	testNum.push_back(vector{54, -1986, 47});
	testNum.push_back(vector{-54, 2021, 37});
	testNum.push_back(vector{-73, -2021, 79});
	printf("n");
	for (auto p = testNum.begin(); p != testNum.end(); ++p) {
		printf("%7d ^ %-7d = %-12d( mod %d )n", (*p)[0], (*p)[1], Pow((*p)[0], (*p)[1], (*p)[2]), (*p)[2]);
	}

	testNum.clear();
	testNum.push_back(vector{2, 100000, 55});
	testNum.push_back(vector{-5, 2020, 248});
	testNum.push_back(vector{43, -3548, 96});
	testNum.push_back(vector{-54, -1986, 47});
	printf("n");
	for (auto p = testNum.begin(); p != testNum.end(); ++p) {
		printf("%7d ^ %-7d = %-12d( mod %d )n", (*p)[0], (*p)[1], Pow((*p)[0], (*p)[1], (*p)[2]), (*p)[2]);
	}

	printf("nn");
}

//Test3.cpp



#include"GlobalSet.h"

static uint Pow_Fermat(int a,int b,uint p) {//使用费马小定理，计算a^b (mod p) 。p为素数，如果不是素数则返回0
	if (IsPrime(p) == false)
		return 0;
	return Pow(a, Mod(b,p-1), p);
}

void Test3() {
	vector>testNum;//格式为[(a,b,p) , (a,b,p) , (a,b,p) ,...]
	testNum.push_back(vector{5, 2020, 23});
	testNum.push_back(vector{43, 3548, 89});
	testNum.push_back(vector{54, -1986, 47});
	testNum.push_back(vector{-54, 2021, 37});
	testNum.push_back(vector{-73, -2021, 79});

	printf("【题目3(使用费马小定理实现模指数运算)】n");
	for (auto p = testNum.begin(); p != testNum.end(); ++p) {
		printf("%7d ^ %-7d = %-12d( mod %d )n", (*p)[0], (*p)[1], Pow_Fermat((*p)[0], (*p)[1], (*p)[2]), (*p)[2]);
	}

	printf("nn");
}

//Test4.cpp



#include"GlobalSet.h"

static uint Pow_Euler(int a, int b, uint p) {//使用欧拉定理，计算a^b (mod p) 
	return Pow(a, Mod(b,PHI(p)), p);
}

void Test4() {
	vector>testNum;//格式为[(a,b,p) , (a,b,p) , (a,b,p) ,...]
	testNum.push_back(vector{2, 100000, 55});
	testNum.push_back(vector{-5, 2020, 248});
	testNum.push_back(vector{43, -3548, 96});
	testNum.push_back(vector{-54, -1986, 47});

	printf("【题目4(使用欧拉定理实现模指数运算)】n");
	for (auto p = testNum.begin(); p != testNum.end(); ++p) {
		printf("%7d ^ %-7d = %-12d( mod %d )n", (*p)[0], (*p)[1], Pow_Euler((*p)[0], (*p)[1], (*p)[2]), (*p)[2]);
	}

	printf("nn");
}

//Test5.cpp

#include"GlobalSet.h"
#include
void Test5() {
	printf("【题目5(手动计算7^{1000}的最后两个数位)】n");

	cout<<"求最后两位数，等价于计算7^1000的模100后的结果，即求解7^1000 (mod 100)"< 

 

 
运行结果