四个TLE

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

sshhgggddsbf @ 2024-06-19 12:09:14

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

by __notTrueLight__ @ 2024-06-19 15:42:18

#include<bits/stdc++.h>
using namespace std;

inline long long gcd(long long a,long long b){
    if(b)return  gcd(b,a%b);
    return a;
}

int main()
{
    int a,b,Dev_C=0,pd=0;
    cin>>a>>b;
    for(int i=1;i<=sqrt(a*b);i++){
        if((a*b)%i==0 && gcd(i,(a*b)/i)==a){
            Dev_C++;
            if(i*i==a*b)pd=1;
        }
    }
    cout<<Dev_C*2-pd;

    return/*191981*/0;
}

|