hdu 1211 RSA (扩展欧几里得算法求逆元 +快速幂)

题目链接

题意:给出p, q, e, l,令n = p * q, fn = (p-1) * (q-1)

给出l个c,计算m = D(c) = cd mod n,其中m为要输入的明文对应的ascii编码,d的计算方法:> calculate d, making d × e mod F(n) = 1 mod F(n), and d will be the private key。

问明文。

 

思路:

出题人JGShining(极光炫影)傻逼。

题意都说不清?

大小写字母一个意思?

脑袋有坑的出题人。

出题人傻逼。

出题人傻逼。

出题人傻逼。

 

 

好了。这道题需要用到扩展欧几里得算法求逆元。。。ksm(a,mod-2)的方法是基于费马小定理,必须mod为质数才可以用。扩展偶记里算法没有这个限制。

用欧几里德算法求模的逆元:

同余方程ax≡b (mod n),如果 gcd(a,n)== 1,则方程只有唯一解。

在这种情况下,如果 b== 1,同余方程就是 ax=1 (mod n ),gcd(a,n)= 1。

这时称求出的 x 为 a 的对模 n 乘法的逆元。

对于同余方程 ax= 1(mod n ), gcd(a,n)= 1 的求解就是求解方程

ax+ ny= 1,x, y 为整数。这个可用扩展欧几里德算法求出,原同余方程的唯一解就是用扩展欧几里德算法得出的 x 。

也就是gcd(a,n,x,y);
然后再(x = x%n + n)%n,得到最小的正整数x,即为a在模n意义下的逆元。

 

 

hdu 1573 X问题 (exgcd求解一般线性同余方程组解的个数)

题目链接

题意:求在小于等于N的正整数中有多少个X满足:X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 < a[i] <= 10)。

思路:先用扩展欧几里得算法(excrt)解一般同余方程求出一个特解R,然后通解R’ = R + k * LCM(a1..am)

注意一些特殊情况,如果无解输出0,如果n小于最小的正整数的R也输出0,

否则答案为(n-R)/M + 1

 

 

poj 2891 Strange Way to Express Integers (扩展欧几里得算法解一般线性同余方程组)

题目链接

题意:给出k个方程,形式为 x%a1==r1,求最小的正数x,无解输出-1.

思路:首先很容易让人联想到crt.

然而crt的使用条件是,所有的m(也就是这道题中的a)两两互质,这道题并不满足,因此不能使用crt.

X mod m1=r1
X mod m2=r2



X mod mn=rn

首先,我们看两个式子的情况
X mod m1=r1……………………………………………………………(1)
X mod m2=r2……………………………………………………………(2)
则有
X=m1*k1+r1………………………………………………………………(*)
X=m2*k2+r2
那么 m1*k1+r1=m2*k2+r2
整理,得
m1*k1-m2*k2=r2-r1
令(a,b,x,y,m)=(m1,m2,k1,k2,r2-r1),原式变成
ax+by=m
熟悉吧?此时,因为GCD(a,b)=1不一定成立,GCD(a,b) | m 也就不一定成立。所以应该先判 若 GCD(a,b) | m 不成立,则方程无解。(理论依据:裴蜀定理
否则,继续往下。

解出(x,y),将k1=x反代回(*),得到X。
于是X就是这两个方程的一个特解,通解就是 X’=X+k*LCM(m1,m2)
这个式子再一变形,得 X’ mod LCM(m1,m2)=X
这个方程一出来,说明我们实现了(1)(2)两个方程的合并。
令 M=LCM(m1,m2),R=r2-r1 注意这里原博客写错了,应该为R=x*m1+r1
就可将合并后的方程记为 X mod M = R。

然后,扩展到n个方程。
用合并后的方程再来和其他的方程按这样的方式进行合并,最后就能只剩下一个方程 X mod M=R,其中 M=LCM(m1,m2,…,mn)。
那么,X便是原模线性方程组的一个特解,通解为 X’=X+k*M。

如果,要得到X的最小正整数解,就还是原来那个方法:

X%=M;
if (X<0) X+=M;

参考博客

这篇题解是我看了那么多讲得最清楚的一篇了….虽然证明的那个地方笔误了。。。好在对照下代码就看出来了(个鬼,我问了好几个人,想到现在。。。最后发现是笔误。好气啊

这道题实际上给出了解线性同余方程组的一般做法(即,不要求所有的m两两互质)

这种做法的理论依据是扩展欧几里得算法,和中国剩余定理没什么关系…

不过既然都是解线性同余方程组。。。非要把这种做法叫什么ex_crt…我也不是很反对….

 

 

 

poj 2142 The Balance (扩展欧几里得算法)

题目链接

题意:给出a,b,d,分别表示a,b两种刻度的砝码,以及要称量的物体重量为d.现在保证能称量出给定重量的物体,问两种砝码个数的和最小的时候,两种砝码分别有多少。如果有多组解,那么要求weight of(ax + by) 最小。

 

思路:求特解直接扩展欧几里得…

关键是怎么找到绝对值和最小的。。

我就是两个方向跑了下。。。

一开始因为把weight of (ax+by)  (求得还是绝对值最小)理解成了 ax+by最小。。导致WA了半天。。。。sigh….

 

 

poj 2115 C Looooops (扩展欧几里得算法)

题目链接

题意: 问 循环for ( int i = a ; i !=b; i+=c)在% (2^k)的意义下循环了多少次。

思路:

一般的思路是:

列方程…

化成扩展欧几里得算法的形式。。。

根据裴蜀定理判断解是否存在…

然后用对用扩展欧几里得算法求出的X,Y按照题目要求调整。

 

poj 1061 青蛙的约会 (扩展欧几里得算法(负数的处理))

 

 

 

题目链接

题意:两只青蛙初始在数轴的x,y点,单位时间内分别可以向右跳m米和n米,数轴是环型的,长度为L,问两只青蛙能否相遇,以及相遇时跳的次数。

思路:相遇就是同一时间在同一地点。

 那么有方程 x+ C*m = y + C*n + k*L 其中C为跳的次数,k为之间差了L的个数(可以理解为被套圈的圈数)

化简得到 C(m-n) + K*L = y-x.

根据裴蜀定理,该方程有解,当且仅当y-x是gcd(m-n,L)的倍数。

然后根据扩展欧几里得算法,需要注意的是其中可能有负数。

如果a是负数,可以把问题转化成

\left|a\right|(-x)+by=\gcd(|a|,b)\left|a\right|为a的绝对值),然后令x'=(-x)

第二个需要注意的是,扩展欧几里得算法求出的是ax+by=gcd(a,b)的解,x,y还要乘对应的倍数才能得到正确的解。

第三个需要注意的是,跳的次数一定为正,这是隐含条件。

用了上道题用的while去得到第一个大于0的X会TLE

所以其实 X = ( X % gx + gx) %gx就好。。。? (其中gx = b/gcd(a,b))

 

 

 

 

hdu 2669 Romantic (扩展欧几里得模板题)

题目链接

题意:问a*x+b*y=1的一组x>0的解,如果无解输出sorry.

思路:根据裴蜀定理, a*x+b*y=1有解当且gcd(a,b)=1。

然后根据扩展欧几里得算法,我们可以得到一组x,y。需要注意的是,这只是其中一组解。

x,y的通解为:(x+k*gx , y-k*gy ) 其中:gx= b/gcd(a,b),gy = a/gcd(a,b),k为任意整数 

 

 

中国剩余定理(crt)学习笔记

 

前置技能点:

维基百科_裴蜀定理(贝祖等式)

对任何整数a, b和它们的最大公约数d,关于未知数xy线性丢番图方程(称为裴蜀等式):ax+by=m

有整数解时当且仅当md倍数。裴蜀等式有解时必然有无穷多个整数解,每组解xy都称为裴蜀数,可用扩展欧几里得算法求得。

特别地,方程 ax+by=1 有整数解当且仅当整数ab互素。(kk:因为1(m=1)只可能是1(d=1)的倍数,也就是说gcd(a,b)=1,即a,b互质)

 

继续阅读“中国剩余定理(crt)学习笔记”