首页 > 其他分享 >基础数论 欧拉定理与exgcd

基础数论 欧拉定理与exgcd

时间:2024-07-26 19:53:14浏览次数:7  
标签:return 数论 res bmod exgcd int ll 欧拉 equiv

欧拉定理:

若正整数 \(a,n\) 互质,则 \(a^{\varphi(p)}\equiv1(\bmod p)\)

推论(扩展欧拉定理):

\[a^b\equiv\begin{cases} a^{b\ \bmod\ \varphi(p)}\ \ \ \ \ \ \ \ \ \gcd(a,p)=1\\ a^b\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \gcd(a,p)!=1,b<\varphi(p)\ \ \ \ \ (\bmod p)\\ a^{b\ \bmod\ \varphi(p)+\varphi(p)}\ \gcd(a,p)!=1,b\geq\varphi(p) \end{cases} \]

证明: \(a^b\equiv a^{b\ \bmod\ \varphi(p)}\ \ \gcd(a,p)=1\)

\[设 b=q\times \varphi(p)+r\\ a^b\equiv a^{q\times\varphi(p)+r}\equiv (a^{\varphi(p)})^q\times a^r\equiv 1^q\times a^r\equiv a^r\equiv a^{b\ \bmod\ \varphi(p)} \]

若正整数 \(a,n\) 互质,则满足 \(a^x\equiv 1(\bmod n)\) 的最小正整数 \(x_0\) 是 \(\varphi(n)\) 的约数。

假设满足 \(a^x\equiv 1(\bmod n)\) 的最小正整数 \(x_0\) 不是 \(\varphi(n)\) 的约数。

设 \(\varphi(n)=qx_0+r(0<r<x_0)\)

\(\therefore a^{x_0}\equiv 1(\bmod n)\)

\(\therefore a^{qx_0}\equiv 1(\bmod n)\)

\(\because a^{\varphi(n)}\equiv 1(\bmod n)\)

\(\therefore a^r\equiv 1(\bmod n)\)

而 \(r<x_0\) ,这与 \(x_0\) 最小矛盾,所以假设不成立。

例: 求 \(a^b\bmod m\) ?

代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e7+10;
int a, m;
char b[maxn];

int phi(int x) {
	int res = x;
	int cnt = sqrt(x);
	for(int i=2; i<=cnt; ++i) {
		if(x % i == 0) {
			res = res / i * (i-1);
			while(x % i == 0) x /= i;
		}
	}
	if(x > 1) res = res / x * (x-1);
	return res;
}

LL quick_pow(LL x, LL y) { 
	LL res = 1;
	while(y) {
		if(y&1)
			res = (res*x)% m;
		x = (x*x) % m;
		y >>= 1;
	}
	return res % m;
}

int main () {
	scanf("%d%d%s", &a, &m, b);
	int Phi = phi(m); // m 的欧拉函数值 
	int rmd = 0;
	int len = strlen(b);
	int flag = 1;
	for(int i=0; i<len; ++i) { // 将 b 对 Phi 取模 
		rmd = rmd * 10;
		if(rmd >= Phi) flag = 0;
		rmd = rmd % Phi;
		rmd = rmd + (b[i]-'0');
		if(rmd >= Phi) flag = 0;
		rmd = rmd % Phi;
	}
	if(flag) // 当 b < Phi 
		printf("%lld\n", quick_pow(a, rmd));
	else printf("%lld\n", quick_pow(a, rmd+Phi));
	return 0;
}

 

相逢是问候

这是一道非常简单且有意思的题:
有两种操作:
\(1\). \(\forall i\in[l,r],a_i=c^{a_i}\)
\(2\). 求\(\sum_{i=1}^na_i\)

对于此题的修改操作,即是求 \(c\) ^ \(c\) ^ \(\cdots\) ^ \(a_i\) \((\bmod p)\) (此处“^”表示乘方)可以证明当层数足够多时其结果为常数。
所以可以使用势能线段树进行修改,对于每个点的修改利用扩展欧拉定理求解,并统计其修改次数,当其足够多时便不用修改。
但是此时 \(3\log\) 的复杂度还不足以通过此题,可以预处理快速幂从而省去一个 \(\log\) 的复杂度即可。

代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;

inline ll read(){
	ll s=0,k=1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-')k=-k;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		s=(s<<3)+(s<<1)+(c^48);
		c=getchar();
	}
	return s*k;
} 

const int N=1e5+10,M=55; 
int n,m,cnt;
ll p,c,a[N],phi[M],op,x,y,Mul1[N][M],Mul2[N][M];
bool fl,f1[N][M],f2[N][M];
struct node{
	ll v,mn;
}t[N<<1];

inline ll Phi(ll V){
	ll res=V,nq=sqrt(V);
	for(register ll i=2;i<=nq;i++){
		if(V%i==0){
			res=res/i*(i-1);
			while(V%i==0) V/=i;
		}
	}
	if(V>1) res=res/V*(V-1);
	return res;
}

inline void init(){
    ll tmp=p; phi[0]=p;
    while(tmp!=1){
    	tmp=Phi(tmp);
		phi[++cnt]=tmp;
	} 
    phi[++cnt]=1;
    for(register int i=0;i<=cnt;i++){ //预处理快速幂
    	Mul1[0][i]=1;Mul2[0][i]=1;
    	for(register int j=1;j<=10000;j++){
    		Mul1[j][i]=Mul1[j-1][i]*c;
    		if(Mul1[j][i]>=phi[i]) 
			Mul1[j][i]%=phi[i],f1[j][i]=1;
    		f1[j][i]|=f1[j-1][i];
		}
		f2[1][i]=f1[10000][i];
        for(register int j=1;j<=10000;++j){
            Mul2[j][i]=Mul2[j-1][i]*Mul1[10000][i];
            if(Mul2[j][i]>=phi[i]) 
			Mul2[j][i]%=phi[i],f2[j][i]=1;
            f2[j][i]|=f2[j-1][i];
        }
	}
}

inline ll ksm(ll t,ll Mod){
	ll mod=phi[Mod];
    ll res,v1=t%10000,v2=t/10000;
    fl=0;
    res=Mul1[v1][Mod]*Mul2[v2][Mod];
    if(res>=mod) res%=mod,fl=1;
    else fl=fl|f1[v1][Mod]|f2[v2][Mod];
    return res;
}

inline ll dfs(ll V,int deep,int pH){ // 运用扩展欧拉定理求答案 c^c^c...^c^ai
    if(deep==pH){
        if(V>=phi[deep]) fl=1,V%=phi[deep];
        return V;
    }
    ll B=dfs(V,deep+1,pH);
    if(fl) return ksm(B+phi[deep+1],deep);
    return ksm(B,deep);
}	

inline void pushup(int s){   // 势能线段树(执行足够多次操作后将会是一个固定值)
	t[s].v=(t[s<<1].v+t[s<<1|1].v);
	if(t[s].v>=p) t[s].v-=p;
	t[s].mn=min(t[s<<1].mn,t[s<<1|1].mn);
}

inline void build(int s,int l,int r){
    if(l==r){
    	t[s].v=a[l];
    	return;
	}
	int mid=(l+r)>>1;
	build(s<<1,l,mid);
	build(s<<1|1,mid+1,r);
	pushup(s);
}

inline void update(int L,int R,int l,int r,int s){
    if(t[s].mn>=cnt) return ;
    if(L==R){
        ++t[s].mn; 
        fl=0;
		t[s].v=dfs(a[L],0,t[s].mn);
        return ;
    }
    int mid=(L+R)>>1;
    if((l<=mid)&&(t[s<<1].mn<cnt)) update(L,mid,l,r,s<<1);
    if((r>mid)&&(t[s<<1|1].mn<cnt)) update(mid+1,R,l,r,s<<1|1);
    pushup(s);
}

inline ll query(int L,int R,int l,int r,int s){
    if((l<=L)&&(R<=r)) return t[s].v;
    int mid=(L+R)>>1;
	ll res=0;
    if(l<=mid) res+=query(L,mid,l,r,s<<1);
    if(res>=p) res-=p;
    if(r>mid) res+=query(mid+1,R,l,r,s<<1|1);
    if(res>=p) res-=p;
    return res;	
}

int main() {
	n=read();m=read();p=read();c=read();
	for(register int i=1;i<=n;i++) a[i]=read();
    build(1,1,n); 
	init();
    while(m--){
        int op,x,y;
        op=read();x=read();y=read();
        if(op==0) update(1,n,x,y,1);
        else printf("%lld\n",query(1,n,x,y,1));
	}
	return 0;
}

 

exgcd:

\(Bézout\): 对于任意整数 \(a,b\) 存在一堆整数 \(x,y\) 满足 \(ax+by=\gcd(a,b)\) 。

在 \(\gcd\) 最后当 \(b=0\) 时,显然 \(x=1,y=0\) 满足 \(a\times1+0\times 0=\gcd(a,0)\) 。

若 \(b>0\) ,则 \(\gcd(a,b)=\gcd(b,a\ {\rm mod}\ b)\) 假设有 \(x,y\) 满足 \(bx+(a\bmod b)y=\gcd(b,a\bmod b)\)

\(bx+(a\bmod b)y=bx+(a-b\lfloor\frac{a}{b}\rfloor)y=ay+b(x-\lfloor\frac{a}{b}\rfloor y)\)

\(\therefore x'=y,y'=x-\lfloor\frac{a}{b}\rfloor y\) 可得 \(ax'+by'=\gcd(a,b)\) 成立。

$\therefore $ 其通解可表示为 \(x=x_0+kb,y=y_0-ka\) 。

模板:

代码
int exgcd(int a, int b, int &x, int &y) {
	if(b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	int d = exgcd(b, a%b, x, y);
	int z = x;
	x = y;
	y = z - (a/b)*y;
	return d; // 返回值是 gcd(a, b); 
} 

对于一般的方程 \(ax+by=c\) ,当且仅当 \(d\mid c\ (d=\gcd(a,b)\ )\) 时有解。

可以先求出 \(ax+by=d\) 的解 \(x_0,y_0\) 易得 \(ax+by=c\) 的解为 \((c/d)x_0,(c/d)y_0\) 。

$\therefore $ 其通解可表示为 \(x=\frac{c}{d}x_0+k\frac{b}{d},y=\frac{c}{d}y_0-k\frac{a}{d}\)

 

求逆元: 即 \(ax\equiv 1(\bmod p)\) 求 \(x\)

\(\because ax\equiv 1(\bmod p),\gcd(a,p)=1\)

\(\therefore ax=1+py\)

\(\therefore ax+p(-y)=1\)

使用 \(exgcd\) 求得 \(x\) 即可。
by ysx

标签:return,数论,res,bmod,exgcd,int,ll,欧拉,equiv
From: https://www.cnblogs.com/classblog/p/18326130

相关文章

  • 基础数论 质数与约数
    基础数论前置芝士:等比数列求和:\(S_n=a_0\frac{1-q^n}{1-q}\)质数与约数:整除与约数设\(n\)为非负整数,\(d\)为正整数,若\(\frac{n}{d}\)为整数,则称\(d\)整除\(n\),记为\(d\midn\)。此时,则称\(d\)是\(n\)的约数,或因数、因子;称\(n\)为\(d\)的倍数。质数......
  • 基础数论 整除分块与欧拉函数
    整除分块:例题:已知\(f(n)=\sum\limits_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor\),给定\(n\),求\(f(n)\)的值。固然可以\(O(n)\)暴力,但显然会\(TLE\)。计算一下前几项的值之后可以发现\(\left\lfloor\frac{n}{i}\right\rfloor\)的取值在连续的一段区间内是......
  • 基础数论 模运算与逆元
    模运算与逆元:取模定义:\[a\bmodn\begin{cases}a-\lfloor\frac{a}{n}\rfloor\timesn\\\\\a\geq0\\-(-a\bmodn)\\\a<0\end{cases}\]取模基本性质:设\(a_0=a\bmodn,b_0=b\bmodn\)\((a+b)\bmodn=((a\bmodn)+(b\bmodn))\bmodn\)......
  • 欧拉路径
    欧拉路径定义欧拉路径,指在有向图$G$中,可以从起点$v_1$​开始,经过每条边,则此路径为欧拉路径。欧拉回路,就是在欧拉路径的基础上,限定终点也必须为$v_1$。判定方法欧拉回路,其实就是一笔画问题。而根据我们的小学数学可知,如果一个图可以一笔画,则必须满足以下条件之一:有两个......
  • 数论
    数论基础整除只在整数域上讨论。一般形式为\(a|b\),叫做\(a\)能整除\(b\)。其性质在此不过多叙述。约数与整除相关。若\(a|b\),则称\(b\)是\(a\)的倍数,\(a\)是\(b\)的约数。在具体问题中,如果没有特别说明,约数总是指正约数。最大公因数和最小公倍数即\((a,b......
  • 【数论】1 矩阵快速幂(斐波那契)
    Tips:本篇blog适合刚开始学习数论部分的同学本题解仅代表个人思路,如有异议欢迎批评指正,谢谢一.概述该章节讲述的是矩阵运算及快速幂的概念,学过的同学可以跳过本章,直接看矩阵快速幂1.矩阵矩阵类似于向量,我们可以这么来表示一个矩阵如上图,表示了一个  的矩阵。矩阵也......
  • AcWing873. 欧拉函数
    题目链接:https://www.acwing.com/problem/content/description/875/题目叙述:给定n个正整数ai,请你求出每个数的欧拉函数。欧拉函数的定义:1∼N中与N互质的数的个数被称为欧拉函数,记为ϕ(N)。输入格式第一行包含整数n。接下来n行,每行包含一个正整数ai。输出格式输出共......
  • 初等数论入门
    整除性定义1如果\(a\)和\(b\)为整数且\(a\neq0\),我们说\(a\)整除\(b\)是指存在整数\(c\)使得\(b=ac\)。如果\(a\)整除\(b\),我们还称\(a\)是\(b\)的一个因子,且称\(b\)是\(a\)的倍数。如果\(a\)整除\(b\),则将其记为\(a|b\),如果\(a\)不能整除\(b\)......
  • 数论函数基础
    数论函数基础数论函数是数论中相当重要的一环,我们先来将*一些基本的函数——\(\color{black}\textsf{H}\color{red}\textsf{\_W\_Y}\)*:同“讲”,讲述全文绝大多数内容是对[0]中讲述的粗略抄写和胡乱加工关于加性函数和积性函数的部分,参考[3]1......
  • 二元一次不定方程(Exgcd)(更方便的解法)
    扩展欧几里得算法(Exgcd)裴蜀定理对于任意一组整数\(a,b\),存在一组整数\(x,y\),满足\(ax+by=\gcd(a,b)\)。Proof:考虑数学归纳法。当\(b=0\)时,由于\(\gcd(a,0)=a\),则对于\(ax+0y=a\)这个不定方程,\(x=1\),\(y\)取任意整数。假设存在一组整数\(x,y\),满足$bx+(a\bmodb)y......