SGU 126 — Boxes
一道数学题…
做法如下:
如果log(2, (a+b)/gcd(a, b))是整数,那么它就是答案;否则无解.
Wind牛的证明如下(有删减):
疾风剑客 01:50:46
很简单- -
疾风剑客 01:50:51
证明
Killa.sqybi 01:50:50
哇
Killa.sqybi 01:50:54
赞..我要听
疾风剑客 01:51:11
显然2个约完该约的是2个奇数吧
疾风剑客 01:51:32
如果2个奇数不相等
疾风剑客 01:51:37
运算1次后
疾风剑客 01:51:42
是2个偶数吧
疾风剑客 01:51:55
然后约掉该约的
疾风剑客 01:52:00
应该又是2个奇数吧
Killa.sqybi 01:52:04
我明白了..
Killa.sqybi 01:52:08
最后约到1 1…
疾风剑客 01:52:17
否则就无解
疾风剑客 01:52:30
而因为每次都是约2
疾风剑客 01:52:35
所以是2^n
疾风剑客 01:52:36
over
看不懂就算了…
网上某牛(flyfox牛吧…)给出的答案有误…
{
SGU 126; Boxes
- sqybi’s code
}
//for my winsty
{$APPTYPE CONSOLE}
program sgu126_sqybi;
const
e = 1e-6;
var
a, b, g: longint;
t: double;
function gcd(x, y: longint): longint;
begin
if y = 0 then
gcd := x
else
gcd := gcd(y, x mod y);
end;
begin
readln(a, b);
if a * b = 0 then begin
writeln(0);
halt;
end;
if a < b then begin
a := a xor b;
b := a xor b;
a := a xor b;
end;
g := gcd(a, b);
t := ln((a+b) div g) / ln(2);
if abs(t-trunc(t)) < e then
writeln(trunc(t))
else
writeln(-1);
readln;
end.
阅读(30 次)