【求助】我脑子笨,穷举超时。
pascal吧
全部回复
仅看楼主
level 9
TAK◆178 楼主
问题描述
对于给定k,求出所有满足1/k=1/x+1/y的x和y的值.
问题输入
整数k(<30000)
问题输出
以x从小到大的顺序输出
输入样例
8
输出样例
1/8=1/9+1/72
1/8=1/10+1/40
1/8=1/12+1/24
1/8=1/16+1/16
代码:
var k,x,y,i:longint;
begin
read(k);
for i:=k+1 downto 1 do
for x:=k+1 to 2*k do
begin
y:=k*i;
if 1/k=1/x+1/y
then begin
writeln('1/',k,'=1/',x,'+1/',y);
break;
end;
end;
end.
输入10000,执行时间为5776ms,而限制时间为1000ms。。。。。
我已经想尽办法了。。。
求解!
2015年07月19日 06点07分 1
level 14
哪个oj的题目?我已写好,试试:
var
k,x,y:longint;
begin
read(k);
for x:=k+1 to k<<1 do
if k*x mod(x-k)=0 then
writeln('1/',k,'=1/',x,'+1/',k*x div(x-k))
end.
2015年07月19日 08点07分 2
嗯嗯。。我傻掉,y好像不用的,拿掉吧。。
2015年07月19日 08点07分
我最近想到一个更好的方法,既然x在不断增大,也就是说y一定持续减小,那么从k(k+1)开始,定义一个起始值,一旦发现成立就将i赋值给起始值,这样循环次数就会减少为大约原来次数的开方,输入200000时间也就435ms。
2015年07月22日 11点07分
回复
������������5
:我的方法改成int64后实测200000就33ms。。
2015年07月22日 14点07分
@139457820 其实说实话你枚举的对象就很有问题。。
2015年07月22日 14点07分
level 6
LZ用哪个测评器的?
2015年07月22日 01点07分 3
cena
2015年07月22日 11点07分
level 11
做过了忘记的路过
2015年07月23日 12点07分 4
1