嘤傻傻

同余方程

对于菜鸟的我来说,连Day2的T1都是如此的困难【手动再见】

同余方程:NOIP 2012 Day2 T1

同余方程,数论题,真巧,我数论也不好。。。

一开始我想的是列举 b 的倍数 by ,当 (by+1)%a==0 时,就输出 (b*y+1)/a 。但是这样的做法不仅超时两个数据,还有四个数据答案错误,最后只有40分(我已经可以预想到我复赛的分数了,呵呵)

然后看了题解,题解一开始也是引入了一个 y ,使式子 ax+by=1 成立,且 y 是个负值。然后用拓展欧几里得算法求得 ax+by=gcd(a,b) 中的未知数( gcd 是一个用来求两个数的最大公约数的函数,自己写的那种),然而在同余方程的证明中,ax+by=m 有解的必要条件是 m mod gcd(a,b)=0 ,所以在这道题中, ax+by=1 的有解必要条件是 1 mod gcd(a,b)=0 ,即 gcd(a,b)=1 ,即 a,b 互质。

简单证明一下为什么 m mod gcd(a,b)=0

因为 gcd 是求最大公倍数,所以可以得知 a 是 gcd(a,b) 的倍数, b 也是 gcd(a,b) 的倍数,然后又因为 m=ax+by ,所以 m 也是 gcd(a,b) 的倍数,所以 m mod gcd(a,b)=0 。

拓展欧几里得

拓展欧几里得是在普通欧几里得算法(辗转相除法)的基础上的,主要是用来在已知 a,b 下求解一组 x,y ,使其满足等式: ax+by=gcd(a,b)(①) 。

根据普通的欧几里得算法, gcd(a,b)=gcd(b,a mod b)(②) 。

假设我们此时已经求得了一组数 x1,y1 ,它们满足 bx1+(a mod b)y1=gcd(b,a mod b) (这个式子是式子②代入①得到的)。将式子②和这个式子进行结合,可以得到 bx1+(a mod b)y1=gcd(a,b) 。所以这时我们只需要求出满足 ax+by=bx1+(a mod b)y1 的 x,y 就行了。

然而在这个时候,这个式子中有了2个未知数 x,y ,求不出唯一解,所以我们就先求出一组必然成立的解,然后在最后时转变成为使 x 为最小正整数的解。

取模的公式为 a mod b=a-b(a/b) ,将其代入我们最新的方程中,解得一个必然存在的解: x=y1,y=x1-(a/b)y1 。这时则需要我们求出 x1,y1 的值。所以我们又要去求 x1,y1 的值,似乎要算很久的样子,但是这个的推导和之前是相似的,我们只需用递归就可以实现了。

最终的答案输出

然而我们在上面求得的 x,y 解不一定能满足 x 是最小整数解。(为什么还不行啊,我要写不下去了,😭)这里的 x 如何使它既不是负数,也不会太大呢?根据公式推导得 x 批量地加上或减去 b ,依然可以使 ax+by=1 。(不想写过程了。。。意会就行)

最终の代码!!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <iostream>

using namespace std;

long long x,y;
void exgcd(long long a,long long b)
{
if(b==0)
{
x=1;y=0;
return ;
}
exgcd(b,a%b);
long long tx=x;
x=y;
y=tx-a/b*y;
}

int main()
{
int a,b;
cin>>a>>b;
exgcd(a,b);
while(x<0)
x+=b;
x%=b;
cout<<x<<endl;
return 0;
}

最终感想

最终的感想是,我真的不想再写数论题正解了,拿个40分真的就可以溜了,看别人的题解写都写了1个小时多,真的可怕。不过在这寒冷的秋夜,得到了老师支援的碗和同学支援的方便面,开森,( •̀ ω •́ )y 。