投稿
  1. 首页
  2. 随笔

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

vpn帐号 • 2022-11-8 • 随笔 • 阅读 13

【C++】【数学】CINTA作业三,第1张

【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 
//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
GlobalSet.cpp 
#include"GlobalSet.h"
#include

vector EGCD(int a, int b) {//新写的EGCD。之前作业二写的EGCD弃用
	struct { int r;  int s;  int val; }//极致压缩？硬写到一行是有够丑的
	M{ 1,0,a }, N{ 0, 1, b };
	auto m = &M;		//[   1   0   a   ]
	auto n = &N;		//[   0   1   b   ]

	while (n->val) {
		auto q = m->val / n->val;
		m->r -= n->r * q;
		m->s -= n->s * q;
		m->val -= n->val * q;

		auto tmp = m;//两指针互换
		m = n;
		n = tmp;
	}
	if (m->val < 0) {
		m->r = -m->r;
		m->s = -m->s;
		m->val = -m->val;
	}
	return vector{ m->r, m->s, m->val};
}

uint Inverse_Multi(int a, uint m) {//模m下a的乘法逆元（无解时返回0
	if (m == 0)
		return 0;
	auto rst = EGCD(a, m);
	return rst[2] == 1 ? rst[0] + (rst[0] < 0 ? m : 0) : 0;
}

uint Mod(int x, uint m) {
	return x > 0 ? (x % m) : (m - (-x) % m);
}

uint Pow(int x, int y, uint m) {//求x^y (mod m)。m=0时不取模
	int rst = 1;
	if (y < 0) {//y为负时取逆元
		x = Inverse_Multi(x, m);
		y = -y;
	}
	if (x == 0)
		return 0;

	if (m == 0) {
		if (x < 0) {
			rst = -1;
			x = -x;
		}
		for (; y; y >>= 1) {
			if (y & 1)
				rst = rst * x;
			x = x * x;
		}
	}
	else {
		x = Mod(x, m);
		for (; y; y >>= 1) {
			if (y & 1)
				rst = Mod(rst * x,m);
			x = Mod(x * x , m);
		}
	}
	return rst;
}


static vector prime{ 2 };//素数集合
static uint buoy = 3;//浮标
static bool Coprime(uint num) {//判断num是否与集合prime的元素互质
	for (auto p = prime.begin(); p != prime.end(); ++p) {
		if (num % *p == 0)
			return false;
	}
	return true;
}


bool IsPrime(uint m) {//判断是否为素数
	if (m < 2)
		return false;
	if(Search(prime,m)!=-1)
		return true;
	if (Coprime(m) == false)
		return false;

	for (uint border = sqrt(m);buoy<=border;++buoy) {//border为遍历边界
		if (Coprime(buoy)) {
			prime.push_back(buoy);
			if (m % buoy == 0)
				return false;
		}
	}
	return true;
}

uint PHI(uint m) {
	if (m == 0)
		return 0;
	map factor;//m的质因数分解
	for (uint border = sqrt(m); buoy <= border; ++buoy) {//border为遍历边界
		if (Coprime(buoy)) 
			prime.push_back(buoy);
	}

	for (auto p = prime.begin(); p != prime.end()&&m!=1; ++p) {
		if (m % (*p) == 0) {
			factor[*p] = 0;
			do {
				m /= (*p);
				++factor[*p];
			} while (m % (*p) == 0);
		}
	}
	if (m != 1)
		factor[m] = 1;
	uint rst = 1;
	for (auto p = factor.begin(); p != factor.end(); ++p) 
		rst *= (p->first - 1) * pow(p->first,p->second-1);
	return rst;
}
Main.cpp 
//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 
//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 
//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 
//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 
//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 
//Test5.cpp

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

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

 

 

运行结果
 

					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://www.outofmemory.cn/zaji/4751691.html
赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
vpn帐号 vpn帐号 一级用户组
0 0
上一篇 2022-11-08
下一篇 2022-11-08

发表评论

登录后才能评论

评论列表（0条）

保存