SGU 330 — Numbers
这道题很神奇…好久没做这么神奇的题目了.
首先对于两个数a,b,如果可以解出的话,一定可以用如下方法解决(一定在500步以内):
首先定义minP(x)为x除了1以外最小的因数.
如果a是奇数,那么a’<-a+minP(a);如果b是奇数,那么b’<-b-minP(b).这样a和b就都成了偶数.
然后假设每次存在最大的k使得a’+2^k<b’,那么让a’<-a’+2^k,直到a’=b’为止.
这样就找到了一个解(a, a’, a”, a”’, …, b’, b).
挺神奇的…
{
SGU 330; Numbers
- sqybi’s code
}
//for my winsty
program sgu330_sqybi;
var
da, db: double;
a, b, pa, pb, t, r: int64;
i, l: longint;
path: array[1..500]of int64;
begin
readln(a, b);
if a = 2 then begin
writeln(’Impossible’);
halt;
end;
da := a;
db := b;
pa := 0;
if odd(a) then begin
for i:=3 to trunc(sqrt(da)) do
if a mod i = 0 then begin
pa := i;
break;
end;
if pa = 0 then begin
writeln(’Impossible’);
halt;
end;
end;
pb := 0;
if odd(b) then begin
for i:=3 to trunc(sqrt(db)) do
if b mod i = 0 then begin
pb := i;
break;
end;
if pb = 0 then begin
writeln(’Impossible’);
halt;
end;
end;
a := a + pa;
b := b - pb;
if a > b then begin
writeln(’Impossible’);
halt;
end;
l := 1;
path[1] := a;
t := 2;
r := 4;
while a <> b do begin
while (a mod r = 0) and (r < a) do begin
t := r;
r := r shl 1;
end;
if a + t > b then break;
inc(l);
a := a + t;
path[l] := a;
end;
while a <> b do begin
while a + t > b do t := t shr 1;
a := a + t;
inc(l);
path[l] := a;
end;
if pa <> 0 then writeln(path[1]-pa);
for i:=1 to l do writeln(path[i]);
if pb <> 0 then writeln(path[l]+pb);
end.
阅读(66 次)