查看原帖
800884
Weekoder楼主2024/10/25 16:51

为什么把 i * i <= x 改成 i <= sqrt(x) 就过了???求解答

AC:

#include <bits/stdc++.h>

#define debug(x) (cout << #x << " " << x << "\n")

using namespace std;

using ll = long long;

ll x, y, ans;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> x >> y;
    int wkd = x;
    x *= y;
    for (int i = 1; i <= sqrt(x); i++) if (x % i == 0 && __gcd(x / i, (ll)i) == wkd) {
        ans += 2 - (i * i == x);
    }    
    cout << ans;
    return 0;
} 

TLE:

#include <bits/stdc++.h>

#define debug(x) (cout << #x << " " << x << "\n")

using namespace std;

using ll = long long;

ll x, y, ans;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> x >> y;
    int wkd = x;
    x *= y;
    for (int i = 1; i * i <= x; i++) if (x % i == 0 && __gcd(x / i, (ll)i) == wkd) {
        ans += 2 - (i * i == x);
    }    
    cout << ans;
    return 0;
} 
2024/10/25 16:51
加载中...