貓の中秋's blog~

扩展的欧几里得辗转相除法

参考《算法艺术与信息学竞赛》219页
令 (a,b)=d, 且 a<=b, 存在 ax+by=d, 求 x,y 可以用扩展的欧几里得辗转相除法.

function extended_gcd(a,b : longint; var x,y:longint):longint;
var
        t : longint;
begin
        if b=0 then begin
                extended_gcd:=a;
                x:=1;
                y:=0;
        end
        else begin
                extended_gcd:=extended_gcd(b, a mod b, x,y);
                t:=x;
                x:=y;
                y:=t-(a div b)*y;
        end;
end;

原书第9行代码有误, 原书为 extended_gcd:=extended_gcd(b, a mod b); , 应为 extended_gcd:=extended_gcd(b, a mod b, x,y);

下面给出推导过程:

若
ax+by=d
(a,b)=d
令
a'=b
b'=a mod b
则
(a',b')=d
假设已求出
a'x'+b'y'=d 有解 x', y'
设 k=a div b, 则
a=ka'+b', b=a'
所以
(ka'+b')x+a'y=d
=> a'(kx+y)+b'x=d
所以可有
kx+y=x'
x=y'
即
x=y'
y=x'-kx=x'-(a' div b')y'

故算法正确

今日失血 200 cc

今日学校组织捐血...... 我很有正义感, 就参加佐.

首先要笃手指验血. 原来我系 B 型血. 某人话 B 型的男好花心, 单系又有人话 B 型系靓仔..囧啊

跟住饮佐杯糖水就去抽血了. 排系我前面有个女的, 左手插佐几次都唔得, 又换右手. 搞到我林翻起小学果时抽血, 两只手笃佐十几次都5得, 真系阴影. 好在我一次过插到血管. 果支针牙签甘粗, 有D恐怖. D血流啊流...N分钟后就搞掂佐.

不过捐完血有5少人晕, 包括某壮男, 不过5包括我 ( 我承认我5系壮男 ).

中午学校仲请吃饭添, 乌鸡汤, 补血. 不错!!
PS: 果个用来渣的波波很好玩.

kvm 下跑 super pi

在带 kvm 的 qemu 里跑了一下 super pi, guest 是 XP SP2

CPU 的性能还是不错的, 在 host 里是 23 秒.

对比没有开 kvm 的

但是运行起来还是比较卡, 感觉是 QEMU 的磁盘 IO 的问题.

//////////////////////////

看一下9佬在 VBox 的测试, 性能很接近

KVM

无 KVM

Wine

隔离班的恶搞墙报

非常强大的东西..

一段超 cheap 的话就填满佐黑板..

LY 版晴天公仔, 含少少暴力