蒟蒻一枚，枚举超时60分，求优化

Karl_Wan @ 2024-08-14 21:55:17

#include <iostream>
using namespace std;
int gcd(int x, int y) {
    if (y == 0) return x;
    return gcd(y, x % y);
}
int ans;
int main() {
    int p, q;
    cin >> p >> q;
    for (int i = 1; i <= q; i++) {
        for (int j = i; j <= q; j++) {
            int g = gcd(i, j);
            if (g == p && (i / g * j) == q) {
                if (i != j) ans += 2;
                else ans++;
            }
        }
    }
    cout << ans;

    return 0;
}

by sxwgysh @ 2024-08-14 22:13:47

#include <iostream>

using namespace std;

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

int p, q;
int sum;

signed main()
{
    cin >> p >> q;
    for(int i = p; i <= q; ++ i)
    {
        int j = p * q / i;
        if(gcd(i, j) == p && i * j / gcd(i, j) == q) sum ++;
    }
    cout << sum << "\n";
    return 0;
}

by amd47802574 @ 2024-08-14 22:35:16

这题是枚举题，
但lg(N²)时间对于本题还是比较大的，
你可以换个思路，定向查找，
是这样的：
当遍历到第i个数，
知道最小公倍数 q = i * j / p，
就可得到另一个数 j = p * q / i，
首先判断j是否合法（p*q%i是否整除），
再通过gcd（）判断i和j最大公约数是不是p。
大功告成！

可以参考我的

LL ans = 0;
LL z = x * y;
for (int i = 0; i < n; i++) {
    int t = (z % v[i] == 0) ? z / v[i] : 1;
    if (t % x == 0 && gcd(v[i], t) == x) ans++;
}

求关(⊙o⊙)

by amd47802574 @ 2024-08-14 22:39:14

@amd47802574 v[ ]是这样的：

vector<int> v;
for (int j = x; j <= y; j += x) v.push_back(j);
int n = v.size();

by Karl_Wan @ 2024-08-15 11:59:50

谢谢各位关照！

by mairuisheng @ 2024-08-15 17:29:03

@KarlWan 我这个可以：

#include<cstdio>
#include<algorithm>
int x,y,i,a,b,r,k,ans;
int main()
{
    scanf("%d %d",&x,&y);
    for(i=x;i<=y;i++)
    {
        if((x*y)%i!=0)continue;
        a=i;
        b=(x*y)/i;
        r=std::__gcd(a,b);
        k=(x*y)/r;
        if(x==r&&y==k)ans++;
    }
    printf("%d",ans);
    return 0;
}