Codeforces Round #426 (Div. 2) C. The Meaningless Game 数论、推公式、分解因数

My Solution

题意：给出n(1 <= n <= 3.5e5)个询问，每个询问给出a、b(1 <= a, b <= 1e9)，A和B 2个人每一轮选择一个数K，如果A先说出就a' * k^2 且B ：b'*K。反之a'*K , b'* K^2, 经过x轮后游戏结束，A最终得分a分，B最中得分为b分(x >= 0)，问得到的a,b是否合理，即是否存在一系列游戏情况使得最终得到a和b值。

数论、推公式、分解因数

a和b初始为1，然后每次一个*k 另一个*K^2,所以最终的结果是a*b = (kk)^3, 其中kk为所以ki的乘积，如果kk存在则合理否则不合理。

这里可以直接使用cmath里的kk = pow((LL)a*b, 1.0 / 3.0), 然后由于pow的各种小误差所以把y = kk和y = kk+1和y = kk-1都带入到公式 a / y * b / y == y这个公式中检查，

只要有其中一个成立则合理，否则不合理。

此外最开始的时候想到了一个笨方法，即所以ki的乘积必定是a，b的gcd的约数，所以每次求出a,b的gcd，然后sqrt(gcd(a,b))的分解因数，最终时间复杂度是O(n*sqrt(1e9))的，开始没有算常数所以以为是1e9的复杂度，后来算上常数发现是1e10的复杂度⊙﹏⊙‖∣。后来才相出这个开3次方的正确方法。

时间复杂度 O(n)

空间复杂度 O(1)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 1e6 + 8;


template 
inline void cinn(T &ret)
{
    char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    ret=c-'0';
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); } int main() { #ifdef LOCAL freopen("c.txt", "r", stdin); //freopen("c.out", "w", stdout); int T = 1; while(T--){ #endif // LOCAL //ios::sync_with_stdio(false); cin.tie(0); LL n, a, b, gcdab, i, ab, len, x; bool ans; cinn(n); while(n--){ cinn(a); cinn(b); //gcdab = gcd(a, b); ab = a*b; ans = false; x = pow(ab, 1.0/3.0); if(a % x == 0 && b % x == 0 && a / x * b / x == x){ ans = true; } x++; if(a % x == 0 && b % x == 0 && a / x * b / x == x){ ans = true; } x -= 2; if(x > 0 && a % x == 0 && b % x == 0 && a / x * b / x == x){
            ans = true;
        }
        if(ans) printf("Yesn");
        else printf("Non");

    }


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx