Codeforces Round #240 DIV1 A問題/DIV2 C問題 - Mashmokh and Numbers

Source

Codeforces Round #240 DIV1 A問題 (500pt)
Codeforces Round #240 DIV2 C問題 (1500pt)
Problem description

問題概要

正整数 $N$ と非負整数 $K$ が与えられる．
要素数 $N$ の数列 $\{a_k\}_{k=1}^N$ で，最初から2項ずつ取り出だせるだけ取り出してGCDを取ったもの和
　$\displaystyle \sum_{k=1}^{\lfloor n/2 \rfloor} {\rm GCD}(a_{2k-1}, a_{2k})$
がちょうど $K$ になるような数列を1つ求める問題．
ただし，$1 \leq a_k \leq 10^9$ を満たし，かつ，同じ要素がない，つまり，$a_i \neq a_j, \;\; i \neq j$ を満たさなければいけない．
存在しないならそれを指摘する．

解法

最初の2項以外は，使わなそうな大きい数字を1ずつずらしながら順番に並べる．
隣り合う整数のGCDは1になるので，必要な残りの数を求めて，最初の2項をその数と，その数の2倍とかにすれば良い．
$N=1$ の時はコーナーケースになるので，場合分けして処理する．
他にもいろいろやり方はあると思う．

C++のスパゲッティなコード

#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<iostream>
#include<cmath>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=_getchar_nolock()
#define mypc(c) _putchar_nolock(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

int res[100010];

int solve(int N, int K){
  int i, j, r;
  
  if(N==1){
    res[0] = 1;
    if(K==0) return 1;
    return 0;
  }

  r = K - N/2 + 1;
  if(r <= 0) return 0;

  res[0] = r;
  res[1] = 2*r;
  j = 1000000000;
  REP(i,2,N) res[i] = j--;
  return 1;
}

int main(){
  int N, K;
  int i;

  reader(&N);
  reader(&K);

  if(solve(N,K)){
    rep(i,N) writer(res[i], i==N-1?'\n':' ');
  } else {
    writer(-1, '\n');
  }

  return 0;
}

Current time: 2024年04月25日13時50分41秒
Last modified: 2014年04月07日04時03分31秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF240 CF_Div1_A CF_Div2_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン：