3个tle,why?

HuangZihan181 @ 2024-02-02 19:21:36

by HuangZihan181 @ 2024-02-02 19:23:43

代码如下

#include<iostream>
using namespace std;
int main(){
    int x,y,sum=0;
    cin>>x>>y;
    int r;
    for(int P=1;P<=y;P++){
        for(int Q=y;Q>=x;Q--){
            int p=P;
            int q=Q;
            r = p % q;
            while (r != 0) {
                p=q;
                q = r;
                r = p % q;
            }
            if(q==x&&P*Q/x==y){
                sum++;
            }
        }
    }
    cout<<sum;
    return 0;
}

by gaojizhe05 @ 2024-02-02 19:31:00

用 gcd 模板求：

long long gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}

by ikun_god @ 2024-02-02 19:45:58

对于 100\% 的数据，2 \le x_0, y_0 \le {10}^5

你这个O(y^2)的时间复杂度肯定会炸。

MY AC CODE(误抄)

#include <bits/stdc++.h>
using namespace std;
int sum[100];
int main(){
    int x,y;
    cin>>x>>y;
    long long sum=0;
    for (int i=x;i<=y;++i){
        //cout<<i<<endl;
        if (y%i==0 && i%x==0){
            if ((x*y)%i==0 && __gcd(i,(x*y)/i)==x){
                //cout<<i<<endl;
                sum+=1;
            }
        }
    }
    cout<<sum<<endl;
    return 0;
}

by ikun_god @ 2024-02-02 19:48:42

话说\gcd不能用STL吗？这么多行STL一个__gcd(int a,int b)不就行了吗？