Codeforces Round #426 (Div. 2) C. The Meaningless Game

90 阅读 0 评论 60 点赞

我是靠谱客的博主有魅力夏天，这篇文章主要介绍Codeforces Round #426 (Div. 2) C. The Meaningless Game，现在分享给大家，希望可以做个参考。

C. The Meaningless Game

题意：

　　两个人刚刚开始游戏的时候的分数，都是一分，然后随机一个人的分数扩大k倍，另一个扩大k的平方倍，问给你一组最后得分，问能不能通过游戏得到这样一组得分。（谁扩大k倍，谁扩大k的平方倍，是可以自由选择的， k的值只要是自然数就行了）。
思路：

　　对输入的两个数a， b。求（a*b) 的1/3次方，如果不能得到，就是不能得的输出“No”。否则在看开方得到的数，能不能同时被a和b整除，如果可以就输出“Yes”，否则就是“No”。

　　本题因为AB卡题了很久，没读懂题，GG所以没怎么写C，早上补一下

用pow函数求 1/3 次方 round是四舍五入

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 10000 + 5;
const int INF = 0x3f3f3f3f;
typedef long long ll;
int n;
void solve (ll a ,ll b)
{
ll c = round( pow(a*b,1.0/3) );
// printf("%dn",c);
if (a%c || b%c || c*c*c != a*b)
printf("Non");
else
printf("Yesn");
}
int main()
{
scanf("%d",&n);
for(int i=0;i < n;i++){
ll a,b;
scanf("%lld %lld",&a,&b);
//
printf("%lld %lldn",a,b);

solve(a,b);
}
return 0;
}

用pow函数写

二分的话左边界是1，右边界是 max(a*b) ^(1/3) 大概做多就是 1e6 再多加2卡一下

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 10000 + 5;
const int INF = 0x3f3f3f3f;
typedef long long ll;
int n;
int main()
{
scanf("%d",&n);
while (n--)
{
ll a,b;
scanf("%lld %lld",&a,&b);
ll le=1,ri= (int)1e6+2;
//printf("%lld %lldn",le,ri);
ll ans = 0;
while (le <= ri)
{
ll mid = (le+ri)/2;
if(mid * mid * mid >= a*b)
ans = mid,ri=mid-1;
else
le = mid+1;
}
if(ans*ans*ans == a*b && a%ans ==0&& b%ans==0)
puts("Yes");
else
puts("No");
}
return 0;
}