_为什么超时_ 本蒟蒻脑子要废了(；′⌒`)

JYF_go @ 2024-06-01 19:55:40

#include <cstdio>
#include <algorithm>
using namespace std;
int q(int a,int b)
{
    while (a % b != 0)
    {
        int r = a % b;
        a = b;
        b = r;
    }
    return b;
}
int n,x,k;
int main()
{
    scanf("%d%d",&n,&x);
    for(int i=n;i<=x;i++)
    {
        for(int j=n;j<=x;j++)
        {
            if(q(i,j)==n&&i*j/q(i,j)==x)
            {
                k++;
            }
        }
    }
    printf("%d",k);
    return 0;
}

by Malkin_Moonlight @ 2024-06-01 20:38:58

你看数据范围，暴力会超时的

by canwen @ 2024-06-18 23:27:40

简单删掉一点多余枚举就能AC了

#include<bits/stdc++.h>
using namespace std;
int main(){
    int x,y;
    cin>>x>>y;
    int ans=0;
    for(int p=1;p<=y;p++){
        if(y%p) continue;
        int q;
        for(q=1;q<=y;q++){
            if(y%q==0&&__gcd(q,p)==x&&p*q / (__gcd(q,p))==y) ans++;
        }
    }
    cout<<ans;
    return 0;
}

by yyc1117 @ 2024-07-12 18:41:16

减半再乘，也能AC

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll x,ll y){
    return y==0? x:gcd(y,x%y);
} 
int main(){
    ll x,y,ans=0;
    cin>>x>>y;
    for(ll i=1;i<=sqrt(x*y);i++)if(x*y%i==0 && gcd(i,x*y/i)==x)ans++;
    ans*=2;
    if(x==y)ans--;
    cout<<ans;
    return 0;
}