TLE，求助

shumu @ 2023-11-16 18:22:15

    #include<bits/stdc++.h>
    using namespace std;
    int gcd(int a,int b) {
        if(b==0) {
            return a;
        }
        else {
            return gcd(b,a%b);
        }
    }
    int lsm(int a,int b) {
        return (a*b)/gcd(a,b); 
    }
    int main() {
        int x,y,ans=0;
        cin>>x>>y;
        for(int i=x;i<=y;i++) {
            for(int j=x;j<=y;j++) {
                if(gcd(i,j)==x&&lsm(i,j)==y) ans++;
            }
        }
        cout<<ans;
        return 0;
    }

by CloudyKai @ 2023-11-16 18:48:53

这个做法是正确的，但复杂度是 O(n^2logn) 的，无法通过本题

你可以尝试枚举 y 的因数

by zyc232008 @ 2023-11-21 17:29:52

    #include<bits/stdc++.h>
    using namespace std;
    int gcd(int a,int b) {
        if(b==0) {
            return a;
        }
        else {
            return gcd(b,a%b);
        }
    }
    int lsm(int a,int b) {
        return (a*b)/gcd(a,b); 
    }
    int main() {
        int x,y,ans=0;
        cin>>x>>y;
        for(int i=x;i<=y;i+=x) {
            for(int j=x;j<=y*x/i;j+=x) {
                if(gcd(i,j)==x&&lsm(i,j)==y) ans++;
            }
        }
        cout<<ans;
        return 0;
    }

加个约束条件及枚举x的因数

by shumu @ 2023-11-30 16:52:04

@CloudyKai 感谢