signed

QiShunwang

“诚信为本、客户至上”

ACM数论题目2 同余方程

2021/4/26 20:04:00   来源:

声明:
题目来源:https://www.luogu.com.cn/problem/P1082

题目描述

求关于 x x x 的同余方程 a x ≡ 1 mod b ax\equiv 1 \textrm{mod}b ax1modb 的最小正整数解。
输入格式
一行,包含两个正整数 a , b a,b a,b 用一个空格隔开。
输出格式
一个正整数 x 0 x_0 x0,即最小正整数解。输入数据保证一定有解。
输入输出样例

输入 #1
3 10

输出 #1
7

说明/提示
【数据范围】
对于 40%的数据,2 ≤b≤ 1,0002≤b≤1,000;
对于 60%的数据,2 ≤b≤ 50,000,0002≤b≤50,000,000;
对于 100%的数据,2 ≤a, b≤ 2,000,000,0002≤a,b≤2,000,000,000。
NOIP 2012 提高组 第二天 第一题

题解思路:

1.拓展欧几里得算法。

分析题目,不难得出下面的式子,
a x + b y = 1 ax+by=1 ax+by=1
我们要做的就是求出x最小的正整数解。
要得到有解的条件,首先要介绍引理1:
引理1: a x + b y = 1 ax+by=1 ax+by=1有解的必要条件。
a s s u m e assume assume t h a t that that a x + b y = k ax+by=k ax+by=k
a ∣ gcd ⁡ ( a , b ) a|\gcd(a,b) agcd(a,b) b ∣ gcd ⁡ ( a , b ) b|\gcd(a,b) bgcd(a,b)
⇒ a x + b y ∣ gcd ⁡ ( a , b ) \Rightarrow ax+by|\gcd(a,b) ax+bygcd(a,b)
⇒ k ∣ gcd ⁡ ( a , b ) \Rightarrow k|\gcd(a,b) kgcd(a,b)
s o so so k  mod  gcd ⁡ ( a , b ) = 0 k\space\textrm{mod}\space\gcd(a,b)=0 k mod gcd(a,b)=0
⇒ gcd ⁡ ( a , b ) = 1 \Rightarrow\gcd(a,b)=1 gcd(a,b)=1
引理2:模余实现方法。
a   m o d   b = a − b [ a b ⌋ a \bmod b=a-b\left[\frac{a}{b}\right\rfloor amodb=ab[ba
例如: 13   m o d   7 = 13 − 7 [ 13 7 ⌋ = 6 13 \bmod 7=13-7\left[\frac{13}{7}\right\rfloor=6 13mod7=137[713=6
其原理可以总结为 a a a 减去 a a a 中含有的最多的 b b b ,减到不能再减为止

a x + b y = gcd ⁡ ( a , b ) = 1 a x+b y=\operatorname{gcd}(a, b)=1 ax+by=gcd(a,b)=1
b x ′ + ( a   m o d   b ) y ′ = gcd ⁡ ( a , b ) = 1 b x^{\prime}+(a \bmod b) y^{\prime}=\operatorname{gcd}(a, b)=1 bx+(amodb)y=gcd(a,b)=1

a x + b y = b x ′ + ( a   m o d   b ) y ′ a x+b y=b x^{\prime}+(a \bmod b) y^{\prime} ax+by=bx+(amodb)y
= b x ′ + a y ′ − b [ a b ⌋ y ′ =b x^{\prime}+a y^{\prime}-b\left[\frac{a}{b}\right\rfloor y^{\prime} =bx+ayb[bay
= a ( y ′ ) + b ( x ′ − ⌊ a b ⌋ y ′ ) =a\left(y^{\prime}\right)+b\left(x^{\prime}-\left\lfloor\frac{a}{b}\right\rfloor y^{\prime}\right) =a(y)+b(xbay)

x ≐ x 1 , y ≐ y 1 , a ≐ a 1 , b ≐ b 1 x \doteq x_{1}, y \doteq y_{1}, a \doteq a_{1}, b \doteq b_{1} xx1,yy1,aa1,bb1
y ′ ≐ x 2 , x ′ − ⌊ a b ⌋ y ′ ≐ y 2 y^{\prime} \doteq x_{2}, x^{\prime}-\left\lfloor\frac{a}{b}\right\rfloor y^{\prime} \doteq y_{2} yx2,xbayy2
x n = y n + 1 , y n = x n + 1 − ⌊ a n b n ⌋ y n + 1 . x_{n}=y_{n+1}, y_{n}=x_{n+1}-\left\lfloor\frac{a_{n}}{b_{n}}\right\rfloor y_{n+1} . xn=yn+1,yn=xn+1bnanyn+1.

a 2 = b 1 , b 2 = a 1   m o d   b 1 a_{2}=b_{1}, b_{2}=a_{1} \bmod b_{1} a2=b1,b2=a1modb1
a n = b n − 1 , b n = a n − 1   m o d   b n − 1 a_{n}=b_{n-1}, b_{n}=a_{n-1} \bmod b_{n-1} an=bn1,bn=an1modbn1

a s s u m e assume assume t h a t that that f ( a , b ) = ( x , y ) f(a, b)=(x, y) f(a,b)=(x,y) m e a n s means means ( x , y ) (x, y) (x,y) s a t i s f y satisfy satisfy t h a t that that e q u a t i o n equation equation a x + b y = 1 ax+by=1 ax+by=1.

f ( a 1 , b 1 ) = ( x 1 , y 1 ) f\left(a_{1}, b_{1}\right)=\left(x_{1}, y_{1}\right) f(a1,b1)=(x1,y1)
f ( a 2 , b 2 ) = ( x 2 , y 2 ) f\left(a_{2}, b_{2}\right)=\left(x_{2}, y_{2}\right) f(a2,b2)=(x2,y2)
u n t i l until until f ( a n , b n ) = ( gcd ⁡ ( a , b ) , 0 ) = ( 1 , 0 ) f\left(a_{n}, b_{n}\right)=(\operatorname{gcd}(a, b), 0)=(1,0) f(an,bn)=(gcd(a,b),0)=(1,0), c a l c u l a t e calculate calculate ( x n − 1 , y n − 1 ) \left(x_{n-1}, y_{n-1}\right) (xn1,yn1) r e v e r s w i c e reverswice reverswice.

f o r for for e x a m p l e example example, a = 3 , b = 10 a=3, b=10 a=3,b=10;
3 x + 10 y = 1 3 x+10 y=1 3x+10y=1;
f ( a 1 , b 1 ) = f ( 3 , 10 ) = ( x 1 , y 1 ) ; f\left(a_{1}, b_{1}\right)=f(3,10)=\left(x_{1}, y_{1}\right) ; f(a1,b1)=f(3,10)=(x1,y1);
f ( a 2 , b 2 ) = f ( 10 , 3 ) = ( x 2 , y 2 ) f\left(a_{2}, b_{2}\right)=f(10,3)=\left(x_{2}, y_{2}\right) f(a2,b2)=f(10,3)=(x2,y2)
f ( a 3 , b 3 ) = f ( 3 , 1 ) = ( x 3 , y 3 ) f\left(a_{3}, b_{3}\right)=f(3,1)=\left(x_{3}, y_{3}\right) f(a3,b3)=f(3,1)=(x3,y3)
f ( a 4 , b 4 ) = f ( 1 , 0 ) = ( x 4 , y 4 ) = ( 1 , 0 ) f\left(a_{4}, b_{4}\right)=f(1,0)=\left(x_{4}, y_{4}\right)=(1,0) f(a4,b4)=f(1,0)=(x4,y4)=(1,0)
x 1 = y 2 = x 3 − ⌊ a 2 b 2 ∣ y 3 = y 4 − ⌊ a 2 b 2 ⌋ ( x 4 − ⌊ a 3 b 3 ⌋ y 4 ) x_{1}=y_{2}=x_{3}-\left\lfloor\frac{a_{2}}{b_{2}} \mid y_{3}=y_{4}-\left\lfloor\frac{a_{2}}{b_{2}}\right\rfloor\left(x_{4}-\left\lfloor\frac{a_{3}}{b_{3}}\right\rfloor y_{4}\right)\right. x1=y2=x3b2a2y3=y4b2a2(x4b3a3y4)
= 0 − ⌊ 10 3 ⌋ ( 1 − ⌊ 3 1 ⌋ ) = − 3 ≡ 7   m o d   10 =0-\left\lfloor\frac{10}{3}\right\rfloor\left(1-\left\lfloor\frac{3}{1}\right\rfloor\right)=-3 \equiv 7 \bmod 10 =0310(113)=37mod10

f o r for for e x a m p l e example example, a = 31 , b = 3731 ; a=31, b=3731 ; a=31,b=3731;
31 x + 3731 y = 1 ; 31 x+3731 y=1 ; 31x+3731y=1;
f ( a 1 , b 1 ) = f ( 31 , 3731 ) = ( x 1 , y 1 ) ; f\left(a_{1}, b_{1}\right)=f(31,3731)=\left(x_{1}, y_{1}\right) ; f(a1,b1)=f(31,3731)=(x1,y1);
f ( a 2 , b 2 ) = f ( 3731 , 31 ) = ( x 2 , y 2 ) ; f\left(a_{2}, b_{2}\right)=f(3731,31)=\left(x_{2}, y_{2}\right) ; f(a2,b2)=f(3731,31)=(x2,y2);
f ( a 3 , b 3 ) = f ( 31 , 11 ) = ( x 3 , y 3 ) ; f\left(a_{3}, b_{3}\right)=f(31,11)=\left(x_{3}, y_{3}\right) ; f(a3,b3)=f(31,11)=(x3,y3);
f ( a 4 , b 4 ) = f ( 11 , 9 ) = ( x 4 , y 4 ) ; f\left(a_{4}, b_{4}\right)=f(11,9)=\left(x_{4}, y_{4}\right) ; f(a4,b4)=f(11,9)=(x4,y4);
f ( a 5 , b 5 ) = f ( 9 , 2 ) = ( x 5 , y 5 ) ; f\left(a_{5}, b_{5}\right)=f(9,2)=\left(x_{5}, y_{5}\right) ; f(a5,b5)=f(9,2)=(x5,y5);
f ( a 6 , b 6 ) = f ( 2 , 1 ) = ( x 6 , y 6 ) ; f\left(a_{6}, b_{6}\right)=f(2,1)=\left(x_{6}, y_{6}\right) ; f(a6,b6)=f(2,1)=(x6,y6);
f ( a 7 , b 7 ) = f ( 1 , 0 ) = ( x 7 , y 7 ) = ( 1 , 0 ) f\left(a_{7}, b_{7}\right)=f(1,0)=\left(x_{7}, y_{7}\right)=(1,0) f(a7,b7)=f(1,0)=(x7,y7)=(1,0)
x 6 = y 7 = 0 ; x_{6}=y_{7}=0 ; x6=y7=0;
y 6 = x 7 − ⌊ a 6 b 6 ∣ y 7 = 1 ; y_{6}=x_{7}-\left\lfloor\frac{a_{6}}{b_{6}} \mid y_{7}=1 ;\right. y6=x7b6a6y7=1;
x 5 = y 6 = 1 x_{5}=y_{6}=1 x5=y6=1
y 5 = x 6 − ⌊ a 5 b 5 ⌋ y 6 = − 4 ; y_{5}=x_{6}-\left\lfloor\frac{a_{5}}{b_{5}}\right\rfloor y_{6}=-4 ; y5=x6b5a5y6=4;
x 4 = y 5 = − 4 ; x_{4}=y_{5}=-4 ; x4=y5=4;
y 4 = x 5 − ⌊ a 4 b 4 ∣ y 5 = 5 ; y_{4}=x_{5}-\left\lfloor\frac{a_{4}}{b_{4}} \mid y_{5}=5 ;\right. y4=x5b4a4y5=5;
x 1 = y 2 = x 3 − ∣ a 2 b 2 ∣ y 3 = y 4 − ⌊ a 2 b 2 ∣ ( x 4 − ⌊ a 3 b 3 ∣ y 4 ) = 5 − ⌊ 3731 31 ] ( − 4 − ∣ 31 11 ∣ × 5 ) x_{1}=y_{2}=x_{3}-\left|\frac{a_{2}}{b_{2}}\right| y_{3}=y_{4}-\left\lfloor\frac{a_{2}}{b_{2}} \mid\left(x_{4}-\left\lfloor\frac{a_{3}}{b_{3}} \mid y_{4}\right)=5-\left\lfloor\frac{3731}{31}\right]\left(-4-\left|\frac{31}{11}\right| \times 5\right)\right.\right. x1=y2=x3b2a2y3=y4b2a2(x4b3a3y4)=5313731](41131×5)
= 1685 =1685 =1685
31 × 1685   m o d   3731 = 1. 31 \times 1685 \bmod 3731=1 . 31×1685mod3731=1.

代码如下:

#include<iostream>

using
		namespace
					std;

pair<int,int> find(int a,int b){
	if(a==1&&b==0) return pair<int,int>(1,0);
	pair<int,int> p=find(b,a%b);
	return pair<int,int>(p.second,p.first-(a/b)*p.second);
}

int refine(int a,int b){
	while(a<0) a+=b;
	a=a%b;
	return a;
}

int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	printf("%d",refine(find(a,b).first,b));
	return EOF+1;
}

2.利用欧拉函数性质。

引理3:欧拉函数幂的同余性质:
s s u m e ssume ssume t h a t that that φ ( b ) \varphi(b) φ(b) i s is is t h e the the E u l e r ′ s Euler's Eulers t o t i e n t totient totient f u n c t i o n function function o f of of b b b
a φ ( b ) ≡ 1   m o d   b a^{\varphi(b)} \equiv 1 \bmod b aφ(b)1modb
通过引理3可以推得下列等式:
a x ≡ 1   m o d   b a x \equiv 1 \bmod b ax1modb
a x ≡ a φ ( b )   m o d   b a x \equiv a^{\varphi(b)} \bmod b axaφ(b)modb
x ≡ a φ ( b ) − 1   m o d   b x \equiv a^{\varphi(b)-1} \bmod b xaφ(b)1modb
可以观察到,方程右边已经没有未知量,考虑到数据范围,只需用Euler筛法筛出 2 × 1 0 9 ⩽ 45 , 000 \sqrt{2 \times 10^{9}} \leqslant 45,000 2×109 45,000以内的质数,只有少于 5000 5000 5000个。
然后计算 的欧拉函数即可。
代码如下:

#include<iostream>
#include<string.h>

#define lint unsigned long long

#define sqmaxn 45000
#define dnprime 4680

using
		namespace
					std;

bool isprime[sqmaxn];
lint prime[dnprime],nprime;

void Euler_mesh(){
	memset(isprime,true,sizeof(isprime));
	nprime=0;
	for(int i=2;i<sqmaxn;i++){
		if(isprime[i]){
			prime[nprime]=i;
			nprime++;
		}
		for(int j=0;i*prime[j]<sqmaxn;j++){
			isprime[i*prime[j]]=false;
			if(i%prime[j]==0) break;
		}
	}
	
}

lint phi(lint x){
	lint ans=1;
	for(int i=0;i<nprime;i++){
		if(x%prime[i]==0){
			x/=prime[i];
			ans*=prime[i]-1;
			while(x%prime[i]==0){
				x/=prime[i];
				ans*=prime[i];
			}
		}
	}
	return x>1?ans*(x-1):ans;
}

lint pow(lint a,lint b,lint mod){
	lint ans=1,base=a;
	while(b>0){
		if(b&1){
			ans=(ans*base)%mod;}
		base=(base*base)%mod;
		b>>=1;
	}
	return ans;
}

signed main(){
	Euler_mesh();
	lint a,b;
	cin>>a>>b;
	cout<<pow(a,phi(b)-1,b);
	return EOF+1;
}