60pts求大神帮助

fanjiayu666 @ 2024-02-27 12:46:23

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

by Jason_Ming @ 2024-02-27 13:27:08

@fanjiayu666 是WA了还是TLE或者其他错误？

by __Tonycyt__ @ 2024-02-27 13:29:40

@Jason_Ming 你自己交一下不就可以了，这种不算抄袭的吧（毕竟都没AC）

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

TLE了

by __Tonycyt__ @ 2024-02-27 13:30:42

@fanjiayu666 你这个的是TLE了，主要是因为算法跑得太慢了

by __Tonycyt__ @ 2024-02-27 13:31:52

如果你学过复杂度的话我可以说得更具体一点，你这个算法是 O(y^2) 的，复杂度太高了

by Jason_Ming @ 2024-02-27 13:33:47

@fanjiayu666 只需要一层循环就可以了

by __Tonycyt__ @ 2024-02-27 13:35:23

你需要优化一下，\gcd(x,y),\operatorname{lcm}(x,y) 表示两个数最大公约数和最小公倍数，那么 \gcd(x,y)\times\operatorname{lcm}(x,y)=xy

by __Tonycyt__ @ 2024-02-27 13:36:13

于是只需要一层循环

by __Tonycyt__ @ 2024-02-27 13:37:33

第二层的 for(int j=1;j<=y;j++) 改成

if(x*y%i!=0) continue
int j=x*y/i; 

by __Tonycyt__ @ 2024-02-27 13:38:01

（不过我好像我少加了个分号）