60pts求大神帮助

P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

@[fanjiayu666](/user/1251774) 是WA了还是TLE或者其他错误?
by Jason_Ming @ 2024-02-27 13:27:08


@[Jason_Ming](/user/1014421) 你自己交一下不就可以了,这种不算抄袭的吧(毕竟都没AC)
by __Tonycyt__ @ 2024-02-27 13:29:40


TLE了
by fanjiayu666 @ 2024-02-27 13:30:41


@[fanjiayu666](/user/1251774) 你这个的是TLE了,主要是因为算法跑得太慢了
by __Tonycyt__ @ 2024-02-27 13:30:42


如果你学过复杂度的话我可以说得更具体一点,你这个算法是 $O(y^2)$ 的,复杂度太高了
by __Tonycyt__ @ 2024-02-27 13:31:52


@[fanjiayu666](/user/1251774) 只需要一层循环就可以了
by Jason_Ming @ 2024-02-27 13:33:47


你需要优化一下,$\gcd(x,y),\operatorname{lcm}(x,y)$ 表示两个数最大公约数和最小公倍数,那么 $\gcd(x,y)\times\operatorname{lcm}(x,y)=xy$
by __Tonycyt__ @ 2024-02-27 13:35:23


于是只需要一层循环
by __Tonycyt__ @ 2024-02-27 13:36:13


第二层的 `for(int j=1;j<=y;j++)` 改成 ```cpp if(x*y%i!=0) continue int j=x*y/i; ```
by __Tonycyt__ @ 2024-02-27 13:37:33


(不过我好像我少加了个分号)
by __Tonycyt__ @ 2024-02-27 13:38:01


| 下一页