80分2个TLE

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

ChasonWang @ 2024-08-27 23:36:45

rt
测试点

#include <bits/stdc++.h>
using namespace std;
int main(){
    int x,y;
    cin>>x>>y;
    int cnt=0;
    for(int i=x;i<=y;i++){
        for(int j=x;j<=y;j++){
            if(i*j==x*y&&__gcd(i,j)==x){
                cnt++;
                break;
            }
        }
    }
    cout<<cnt;
    return 0;
}

by ChasonWang @ 2024-08-27 23:37:31

玄关

by nxd_oxm @ 2024-08-28 08:06:33

你可以去掉一个循环。因为 i \times j = x \times y，所以 x\times y \div i=j。

for(int i=x;i<=y;i++){
    if(x*y%i!=0)continue;
  int j=x*y/i;
    if(__gcd(i,j)==x){
        cnt++;
        break;
    }
}

by ChasonWang @ 2024-08-28 08:35:25

@xiangqizhen2011 秒变30，其余wa

by nxd_oxm @ 2024-08-28 12:06:41

```cpp for(int i=x;i<=x*y;i++){ if(x*y%i!=0)continue; int j=x*y/i; if(__gcd(i,j)==x){ cnt++; break; } } ```

by ChasonWang @ 2024-08-28 21:14:54

wa

by LEZ11821111 @ 2024-08-31 19:51:41

去掉break，去掉第二个循环，第一个条件改成 i*j/x==y。

by LEZ11821111 @ 2024-08-31 19:53:25

给你参考一下：

#include<bits/stdc++.h> 
using namespace std;
int x,y,c,i,j;
int main()
{
    cin>>x>>y;
    for(i=x;i<=y;i++){
        j=x*y/i;
        if(__gcd(i,j)==x&&i*j/__gcd(i,j)==y)c++;
    }
    cout<<c;
    return 0;
}

by LEZ11821111 @ 2024-09-08 12:47:21

能过吗？

by ChasonWang @ 2024-09-08 13:14:36

@LEZ11821111 过了

by ChasonWang @ 2024-09-08 13:15:05

已关
此贴完

|