现在的位置: 首页 > 综合 > 正文

CodeForces 414A Mashmokh and Numbers

2017年10月13日 ⁄ 综合 ⁄ 共 836字 ⁄ 字号 评论关闭

题目链接:点击打开链接

题目的意思就是,一次顺序取两个点,直到取的还剩下1个或者0个。求这样一个序列使得所取的所有的两两数的gcd和正好为k。

比赛的时候,稍微的想了一下思路,感觉好像,很麻烦的样子,当时,还没有意识到该种序列是多种的,没有继续深想下去。

思路的话,当时是这么想的,

第一,只要n/2>k,肯定就是-1。

第二,就是可能存在这种序列,然后根据需要达到的k,进行分摊,比如如果k=6,而对数仅仅是3的话,那么,每对的gcd=2就好;再如k=7的话,那么,对数还是3的话,gcd1=3,gcd2=2,gcd3=2。

这种想法,应该是对的,但是处理来好像很麻烦的样子,也就没有深入的再想。

后来,下来看题解:

思路的这样的:

第一:同上第一。

第二:和一开始的思路有点差异,这种思路就是直接让第一对gcd=k-(n/2-1)。然后,后面的直接全部gcd=1就好。

还有一种特殊的情况就是,不需要数对就是可以胜利的,k=0,c=0,只需要一个数就好。这个数也是随机的。

唯一让我担忧是后面的数对,会不会超出10^9。

后来,计算一下,没有问题。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int main(){
    int n,k;
    while(~scanf("%d%d",&n,&k)){
        int cnt=n/2;
        if(cnt==0&&k==0){
            puts("1");
        }
        else if(cnt>k||cnt==0){
            puts("-1");
        }
        else {
            int x=k-(cnt-1);
            printf("%d %d",x,x*k);//k的取值是不固定的,因为,1和任意k的gcd都为1,只要保证接下来的数是在数据范围内就好.
            x=x*k+1;
            n=n-2;
            while(n--){
                printf(" %d",x++);
            }
            puts("");
        }
    }
    return 0;
}

构造题。

比赛的时候,要勇于尝试。


抱歉!评论已关闭.