警示后人 如果你 #6 TLE

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

Genius_Star @ 2023-07-29 15:21:44

如果你 #6 TLE：

那么请检查，你是否写的是以下代码：

for(int i=1;i*i<=P*Q;i++)

如果是，那么请将 i 开为 long long，如果你执意不开 long long 的话，可以修改为以下形式：

for(int i=1;i<=sqrt(P*Q);i++)

原因：：

因为 P \times Q 最大为 10^{10}，在枚举它的约数时如果是 i \times i 这样判断是否到了根号，如果 i 是 int 类型将会爆。

但是对于 \sqrt{P \times Q}，其范围在 10^5 以内，所以可以通过。

关于 TLE 的原因是，如果你的数爆了一个类型，那么该值将会随机赋值为极大或者极小的数。

注： 如果你要使用 STL 库里面的 sqrt 函数，那么请使用 math.h 或者万能头文件。

by wangyinghao @ 2023-08-03 14:24:28

@Genius_Star 感谢！！！！！！！！

by Linrui0812 @ 2023-08-04 23:00:25

@Genius_Star 谢谢dalao赐教！蒟蒻明白了！

by Linrui0812 @ 2023-08-04 23:05:16

dalao，<math.h>应该是<cmath>吧

by Linrui0812 @ 2023-08-04 23:05:38

@Genius_Star

by Genius_Star @ 2023-08-04 23:10:31

@Linrui0812 都可以，不信你试试

by Linrui0812 @ 2023-08-04 23:50:44

@Genius_Star 小蒟蒻收到！ 谢谢dalao到现在还回复小蒟蒻，真是谢谢dalao！ （蒟蒻准初一）

by uLto @ 2023-08-10 15:04:36

是不是可以只从P遍历到Q

    for(int i=m;i<=n;i++){
        int k=m*n/i;
        int s=gcd(i,k);
        if(s==m&&i*k==n*m){
            ans++;
        } 
    }

by 01Dragon @ 2024-06-09 19:04:55

谢谢

|