首页 > 其他分享 >同余

同余

时间:2023-07-03 17:15:00浏览次数:37  
标签:return int ll long exgcd include 同余

 求逆

例题1:P1082 [NOIP2012 提高组] 同余方程

模板题,使用拓展欧几里得算法求逆

代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll gcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1;y=0;
		return a;
	}
	ll d=gcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
ll inverse(ll a,ll m){
	ll x,y;
	gcd(a,m,x,y);
	return (x%m+m)%m;
}
int main(){
	ll a,m;cin>>a>>m;
	cout<<inverse(a,m);
	return 0;
}

  

例题2:poj2115  C Looooops

使用裴蜀定理判断是否有解,再求逆

代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
ll gcd(ll a,ll b){
	if(!b)return a;
	return gcd(b,a%b);
}
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1;y=0;
		return a;
	}
	ll d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
int main(){
	ll a,b,c,k;
	while(cin>>a>>b>>c>>k){
		if(a==0&&b==0&&c==0&&k==0)break;
		ll B=1LL<<k,x,y;
		exgcd(c,B,x,y);
		if((b-a)%gcd(c,B)==0){
			x*=(b-a)/gcd(c,B);
			ll m=B/gcd(c,B);
			cout<<(x%m+m)%m<<'\n';
		}else cout<<"FOREVER\n";
	}
	return 0;
}

 

例题3:P3811 【模板】乘法逆元

使用递推式 inv[i]=(m-m/i)*inv[m%i]%m来求乘法逆元

代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e6+39+7;
ll inv[N];
void inverse(ll n,ll p){
	inv[1]=1;
	for(int i=2;i<=n;i++)inv[i]=(p-p/i)*inv[p%i]%p;
}
int main(){
	ll n,p;cin>>n>>p;
	inverse(n,p);
	for(int i=1;i<=n;i++)cout<<inv[i]<<'\n';
	return 0;
}

  

例题4:hdu1576  A/B

求逆元,得到k/n,在乘n,得到结果

代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1;y=0;
		return a;
	}
	ll d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
int main(){
	ll n,b,T,x,y;cin>>T;
	while(T--){
		x=y=0;
		cin>>n>>b;
		exgcd(b,9973,x,y);
		x=(x+9973)%9973;
		cout<<x*n%9973<<'\n';
	}
	return 0;
}

  

例题4:hdu5976  Detachment

使用逆元计算除法取模,再用二分加前缀和与连续积来计算

代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+39+7,MOD = 1e9+7;
ll sum[N],mul[N],inv[N];
void init(){
	inv[1]=1;sum[1]=0,mul[1]=1;
	for(int i=2;i<50000;i++){
		sum[i]=sum[i-1]+i;
		mul[i]=(mul[i-1]*i)%MOD;
		inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	init();
	int T;cin>>T;
	while(T--){
		int x;cin>>x;
		if(x==1){
			cout<<1<<'\n';
			continue;
		}
		int k=upper_bound(sum+1,sum+50000+1,x)-sum-1;
		int m=x-sum[k];
		if(k==m)cout<<mul[k]*inv[2]%MOD*(k+2)%MOD<<'\n';
		else cout<<mul[k+1]*inv[k-m+1]%MOD<<'\n';
	}
	return 0;
}

  

中国剩余定理

例题:P4777 【模板】扩展中国剩余定理(EXCRT)

使用迭代法,不断合并方程式,得到答案

代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+39+7;
int n;ll ai[N],mi[N];
ll quickMul(ll a,ll b,ll m){
	ll ans=0;
	while(b){
		if(b&1)ans=(ans+a)%m;
		a=(a+a)%m;
		b>>=1;
	}
	return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1;y=0;
		return a;
	}
	ll d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
ll EXCRT(){
	ll x,y,a1=ai[1],m1=mi[1],ans=0;
	for(int i=2;i<=n;i++){
		ll a2=ai[i],m2=mi[i];
		ll a=m1,b=m2,c=(a2-a1%m2+m2)%m2;
		ll d=exgcd(a,b,x,y);
		if(c%d)return -1;
		x=quickMul(x,c/d,b/d);
		ans=a1+x*m1;
		m1=m2/d*m1;
		ans=(ans%m1+m1)%m1;
		a1=ans;
	}
	return ans;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>mi[i]>>ai[i];
	cout<<EXCRT();
	return 0;
}

  

标签:return,int,ll,long,exgcd,include,同余
From: https://www.cnblogs.com/zhanghx-blogs/p/17523356.html

相关文章

  • 同余——推柿子
    同余——推柿子eg1.[P1516青蛙的约会](P1516青蛙的约会-洛谷|计算机科学教育新生态(luogu.com.cn))题意:设青蛙A的出发点坐标是\(x\),青蛙\(B\)的出发点坐标是\(y\)。青蛙\(A\)一次能跳\(m\)米,青蛙\(B\)一次能跳\(n\)米,两只青蛙跳一次所花费的时间相同。纬度......
  • k 倍区间(同余定理,组合数)
    题目描述给定一个长度为 N 的数列,1,2,⋯A1​,A2​,⋯AN​,如果其中一段连续的子序列 ,+1,⋯(≤)Ai​,Ai+1​,⋯Aj​(i≤j) 之和是 K 的倍数,我们就称这个区间 [,][i,j] 是 K 倍区间。你能求出数列中总共有多少个 K 倍区间吗?输入格式第一行包含两个整数 N 和 K......
  • 初等数论(Ⅲ):高次同余、阶和原根相关
    前言关于高次同余方程,有\(a^x\equivb(\text{mod}\p)\)和\(x^a\equivb(\text{mod}\p)\)两种类型,后者计算起来较为麻烦,下文就分别记述这两种高次同余方程。离散对数问题离散对数问题是在模\(p\)意义下求解\(\log_ab\),这等价于形如\[a^x\equivb(\text{mod}\p)......
  • 浅谈同余3(扩展中国剩余定理,扩展BSGS)
    距离上一篇已经四个月了,我来填坑了上一篇:$浅谈同余2(扩展欧几里得,中国剩余定理,BSGS)$(https://www.cnblogs.com/xyy-yyds/p/17418472.html)0x50扩展BSGS$O(\sqrtn)$【模板】扩展BSGS/exBSGS 题目背景题目来源:SPOJ3105Mod题目描述给定$a,p,b$,求满足$a^x≡b\pmodp......
  • 浅谈同余1(常用定理和乘法逆元)
    点个赞吧,球球了~下一篇:$浅谈同余2(扩展欧几里得,中国剩余定理,BSGS)$https://www.acwing.com/file_system/file/content/whole/index/content/7882318/ $\LaTeX$太多了,分成几个部分0x00总写(瞎说)同余是数学中非常重要的东西,这里会写出同余的基本运用若$a\bmodm=b\bmo......
  • [基础数论]同余方程笔记
    前言在学习本节内容前,请确保已完成了二元不定方程的学习。同余方程有无解的判别对于一个方程形如:\[ax\equivb\pmodm\]其中\[a,b\in\mathbbZ,m\in\mathbbZ^+\]并令\[d=(a,m)\]若\(d\nmidb\),则方程\(ax\equivb\pmodm\)无解。若\(d\midb\),......
  • 同余的基本性质
    同余的基本性质注:这里默认$a,b,c,d\in\mathbb{Z},m,k,d\in\mathbb{Z}^+$若$a_1\equivb_1\pmodm$,\(a_2\equivb_2\pmodm\),则\(a_1\pma_2\equivb_1\pmb_2\pmodm\).若$a_1\equivb_1\pmodm$,\(a_2\equivb_2\pm......
  • 同余类与剩余系
    来自潘承洞、潘承彪《初等数论》,有删改。定义1(同余类)把全体整数分为若干个两两不相交的集合,使得\((i)\)在同一个集合中的任两个数模\(m\)一定同余;\((ii)\)在两个不同集合中的任两个数模\(m\)一定不同余。每一个这样的集合称为模\(m\)的同余类。我们以\(r\bmodm\)......
  • 同余的定义以及基本性质学习笔记
    来自潘承洞、潘承彪《初等数论》,有删改。一、定义定义1(同余)设\(m\ne0\)。若\(m\mida-b\),即\(a-b=km\),则称\(m\)为模,\(a\)同余于\(b\)模\(m\)以及\(b\)是\(a\)对模\(m\)的剩余,记作\[a\equivb\pmodm(1)\]否则,则称\(a\)不同余于\(b\)模\(m\),\(b\)不......
  • 同余方程学习笔记
    一、裴蜀定理裴蜀定理(或贝祖定理)得名于法国数学家艾蒂安·裴蜀,说明了对任何整数\(a,b\)和它们的最大公约数\(d\),关于未知数\(x\)和\(y\)的线性不定方程(称为裴蜀等式):若\(a,b\)是整数,且\(\gcd(a,b)=d\),那么对于任意的整数\(x,y,ax+by\)都一定是\(d\)的倍数。特别地,......