C++枚举4个TLE,60分!

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

wangruize88 @ 2023-10-05 12:16:45

#include <bits/stdc++.h>
using namespace std ;
int gcd ( int a , int b ) {
    int maxn = max ( a , b ) , minn = min ( a , b ) ;
    while ( maxn % minn != 0 ) {
        int n = maxn ;
        maxn = minn , minn = n % minn ;
    }
    return minn ;
}
int lcm ( int a , int b ) {
    return a * b / gcd ( a , b ) ;
}
int main () {
    int x , y , ans = 0 ;
    cin >> x >> y ;
    for ( int i = x ; i <= y ; i ++ ) {
        for ( int j = x ; j <= y ; j ++ ) {
            if ( gcd ( i , j ) == x && lcm ( i , j ) == y ) ans ++ ;
        }
    }
    cout << ans ;
    return 0 ;
}

by Composite_Function @ 2023-10-05 12:29:38

你这样的代码是 O((y-x)^2) 的,,当然会 T

你可以这么写:

y *= x; // 由于两个数的 gcd * lcm 为两数之积
for (int i = 1; i * i <= y; ++i)
  if (n % i == 0 && __gcd(n, n / i) == x)
    ans += 2; // 统计两次

|