Codeforces Round #426 (Div. 2)

题目链接：http://codeforces.com/contest/834/problem/C

题意：两个在玩一个游戏，对于每一轮，选定一个自然是k，初始两人的分数都为1，每一个回合赢的人在他当前分数的基础上乘以k^2,输的人在他当前分数的基础上乘以k,现在经过若干回合后他们的分数分别是a,b问你这个a,b是否合法。

思路：首先对于每一个回合，赢的人乘以k^2,输的人乘以k,那么对于k来说每一个回合对于两个的总贡献就是k^3，不管3个k怎么分配的这两个人。所以两个人的总分数(a*b)一定是一个三次方数。所以可以二分k，找到一个k满足k^3==a*b。并且还要满足a%k==0&&b%k==0,因为每次a和b都是乘以k(不管乘了1次还是2次)，所以a和b一定要是k的倍数。

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<string>

#include<queue>

#include<vector>

#include<time.h>

#include<cmath>

#include<set>

#include<map>

using namespace std;

typedef long long int LL;

const int MAXN = 1e6 + ;

const int INF = 1e9;

const int mod = 1e9 + ;

int main(){

#ifdef kirito

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    int n, a, b;

    while (~scanf("%d", &n)){

        for (int i = ; i <= n; i++){

            scanf("%d%d", &a, &b);

            int l = , r = , mid;

            while (r >= l){

                mid = (l + r) >> ;

                if (1LL * mid*mid*mid >= 1LL * a*b){

                    r = mid - ;

                }

                else{

                    l = mid + ;

                }

            }

            int k = l;

            if ((1LL * k*k*k == 1LL * a*b) && (a%k == ) && (b%k == )){

                printf("Yes\n");

            }

            else{

                printf("No\n");

            }

        }

    }

    return ;

}

巴特西

Codeforces Round #426 (Div. 2) - C

最新文章

热门文章