InTheBloodHorse

每日一题(34) codeforces1059C

字数统计: 226阅读时长: 1 min
2018/10/17 Share

题目地址

题意

给一个数字n,每次从这n中删除一个数字,删除前计算数字里面的gcd,问如何删除,可以使得gcd最大。

思路

因为相邻的两个数字是互质的,所以我们要删除奇数,因为当所有的奇数删完之后,每次计算的gcd肯定是大于等于2的。
奇数删完后,把奇数位置的数字当奇数,再筛选,输出,直到没有。
AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int ans=1;
while(n>3){
for(int i=0;i<n/2+n%2;i++){
cout << ans << " ";
}
n>>=1;
ans<<=1;
}
if(n==3) cout << ans << " " << ans << " " << ans*3 << endl;
else if(n==2) cout << ans << " " << ans*2 << endl;
else cout << ans << endl;
}

原文作者:InTheBloodHorse

原文链接:http://pyking.cn/2018/10/17/每日一题-34-codeforces1059C/

发表日期:October 17th 2018, 1:33:04 pm

更新日期:October 17th 2018, 1:40:30 pm

版权声明:Have a fun

CATALOG
  1. 1. 题意
  2. 2. 思路