首页 > 其他分享 >整数取模类

整数取模类

时间:2024-11-05 22:08:32浏览次数:1  
标签:ModInteger const rhs 整数 取模类 num operator return

实现一个整数取模类(加减乘除均可)。

template<int Mod, typename T = int> class ModInteger {
private:
	T x; // 数值本身,类型默认为 int
private:
	static T increase(const T &num) { return num >= Mod ? num - Mod : num; }
	static T decrease(const T &num) { return num < 0 ? num + Mod : num; }
public:
	ModInteger() : x(0) { }
	ModInteger(T num) : x(num >= 0 ? num % Mod : (Mod - (-num) % Mod) % Mod) { }
	ModInteger inverse() const {
		T a = x, u = 1, v = 0, k = 0; // 扩展欧几里得求逆元
		int b = Mod;
		while (b > 0) {
			k = a / b;
			swap(a -= k * b, b);
			swap(u -= k * v, v);
		}
		return ModInteger(u);
	}
	static ModInteger pow(ModInteger a, ll b) {
		ModInteger res(1); // 快速幂,静态成员函数,可直接在外部调用。
		while (b) {
			if (b & 1) res *= a;
			a *= a;
			b >>= 1;
		}
		return res;
	}
	ModInteger pow(ll b) const { return pow(*this, b); } // 快速幂,成员函数。
	ModInteger operator-() const { return ModInteger(-x); }
	ModInteger &operator+=(const ModInteger &rhs) { x = increase(x + rhs.x); return *this; }
	ModInteger &operator-=(const ModInteger &rhs) { x = decrease(x - rhs.x); return *this; }
	ModInteger &operator*=(const ModInteger &rhs) { x = 1ll * x * rhs.x % Mod; return *this; }
	ModInteger &operator/=(const ModInteger &rhs) { *this *= rhs.inverse(); return *this; } // 除以就相当于乘以逆元
	friend ModInteger operator+(const ModInteger &lhs, const ModInteger &rhs) { return ModInteger(lhs) += rhs; }
	friend ModInteger operator-(const ModInteger &lhs, const ModInteger &rhs) { return ModInteger(lhs) -= rhs; }
	friend ModInteger operator*(const ModInteger &lhs, const ModInteger &rhs) { return ModInteger(lhs) *= rhs; }
	friend ModInteger operator/(const ModInteger &lhs, const ModInteger &rhs) { return ModInteger(lhs) /= rhs; }
	
	bool operator==(const ModInteger &rhs) const { return x == rhs.x; }
	bool operator!=(const ModInteger &rhs) const { return x != rhs.x; }
	bool operator>=(const ModInteger &rhs) const { return x >= rhs.x; }
	bool operator<=(const ModInteger &rhs) const { return x <= rhs.x; }
	bool operator>(const ModInteger &rhs) const { return x > rhs.x; }
	bool operator<(const ModInteger &rhs) const { return x < rhs.x; }
	
    T data() const { return x; } // 获取数值
    
	friend ostream &operator<<(ostream &os, const ModInteger &num) { return os << num.x; }
	friend istream &operator>>(istream &is, ModInteger &num) {
		T input;
		is >> input;
		num = ModInteger(input);
		return is;
	}
};

标签:ModInteger,const,rhs,整数,取模类,num,operator,return
From: https://www.cnblogs.com/jxyanglinus/p/18528981

相关文章

  • C语言实现一个打印非负整数阶乘的函数
    简单版阶层计算升级版阶层计算(c语言的基本类型不能存储)简单版阶层计算:其中N是用户传入的参数,其值不超过12。如果N是非负整数,则该函数必须返回N的阶乘,否则返回0裁判测试程序样例:#include<stdio.h>intFactorial(constintN);intmain(){intN,NF;s......
  • 用pandas 读取excel文件,存到数组中,调整数组的值
    importpandasaspdimportpymysqlfromdatetimeimportdatetime#定义一个自增的全局变量counter=1defincrement():globalcountercounter+=1returncounter#调用函数并打印结果#print(get_current_date())defget_array():#读取Excel......
  • C++——用指向指针的指针的方法对n个整数排序并输出。要求将排序单独写成一个团数,整数
    没注释的源代码#include<iostream>usingnamespacestd;voidsortNumbers(int**arr,intn);intmain(){  intn;  cout<<"enterthenumberofintegers:";  cin>>n;  int**arr=newint*[n];  for(inti=0;i<n;i++)  {......
  • C++——输入一个字符串,内有数字和非数字字符,如a123x456_ 17960?302tab5876将其中连续
    没注释的源代码#include<iostream>#include<stdio.h>usingnamespacestd;intmain(){  charstr[50],*pstr;  inti,j,k,m,e10,digit,ndigit,a[10],*pa;  cout<<"pleaseinputstring:"<<endl;  gets(str);  pstr=&str[......
  • LeetCode题练习与总结:两整数之和--371
    一、题目描述给你两个整数 a 和 b ,不使用 运算符 + 和 - ,计算并返回两整数之和。示例1:输入:a=1,b=2输出:3示例2:输入:a=2,b=3输出:5提示:-1000<=a,b<=1000二、解题思路这个问题可以通过位运算来解决。位运算中的“与”操作(&)和“异或”操作(^......
  • Leetcode每日一题 3226. 使两个整数相等的位更改次数
    Leetcode每日一题##3226.使两个整数相等的位更改次数###C++给你两个正整数n和k。你可以选择n的二进制表示中任意一个值为1的位,并将其改为0。返回使得n等于k所需要的更改次数。如果无法实现,返回-1。解题思路:通过除2取余依次获得两个数对应的二进制位......
  • 力扣题目解析--整数转罗马数
    题目七个不同的符号代表罗马数字,其值如下:符号值I1V5X10L50C100D500M1000罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则:如果该值不是以4或9开头,请选择可以从输入中减去的最大值的符号,将该符号附加到结果,减去其值,然后将......
  • 今日力扣:3226. 使两个整数相等的位更改次数 python3解法
    给你两个正整数 n 和 k。你可以选择 n 的 二进制表示 中任意一个值为1的位,并将其改为0。返回使得 n 等于 k 所需要的更改次数。如果无法实现,返回-1。示例1:输入: n=13,k=4输出: 2解释:最初,n 和 k 的二进制表示分别为 n=(1101)2 和 k=(010......
  • Leetcode 3226. 使两个整数相等的位更改次数
    模拟题,但是要注意按位与操作和比较运算符的优先级,比较运算符优先级更高,所以t1,t2这样写,不然就得加括号。1classSolution{2public:3intminChanges(intn,intk){4intres=0;5while(n&&k){6intt1=n&1;7int......
  • 整数二分 ——洛谷p9240冶炼金属
    #include<bits/stdc++.h>#defineendl'\n'#defineINF0x3f3f3f3f#defineintlonglongusingnamespacestd;constintN=1e4+10;inta[N],b[N];intn;//找左节点boolcheck_min(intmid){ for(inti=0;i<n;i++) { if(b[i]<a[i]/mid) return......