1 条题解
-
0
题解代码：
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 5; void solve(){ int x,y; cin >> x >> y; int ans = 0; for(int i = 1;i <= sqrt(x*y); i++){ if(x * y % i == 0 && gcd(i, x * y / i) == x) ans++; } cout << (x != y ? ans * 2 : ans * 2 -1) << endl; } signed main(){ ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int T = 1; // cin >> T; while(T--){ solve(); } return 0; }-
morgen
@ 2025-10-12 21:10:21
根据题目容易写出来的代码（超时）。
int x,y; cin >> x >> y; int sum = 0; for(int i = 1; i <= y; i++){ for(int j = 1; j <= y; j++){ if(gcd(i,j) == x && i * j == y * x){ sum++; } } } cout << sum << endl;这样超时该怎么优化呢？ 思路： 枚举
x*y的因子for(int i = 1;i <= sqrt(x*y); i++){ if(x * y % i == 0 && gcd(i, x * y / i) == x) ans++; }超时代码通过双层循环枚举
i,j（范围至y），时间复杂度为O(y²)，效率极低。优化后，利用 “因子成对性”：对于
n = x*y，其因子i和j = n/i成对出现，只需枚举i至sqrt(n)即可覆盖所有因子对，时间复杂度降至O(sqrt(x*y))， 足以通过该题。
-
- 1