Educational Codeforces Round 011 A. Co-prime Array

문제

https://codeforces.com/contest/660/problem/A

Problem - A - Codeforces

 

문제요약

n개의 수열이 주어질 때 수열 내의 임의의 인접한 두 수의 gcd가 1이 아닌 경우 사이에 수들을 넣어 수열 전체에서 임의의 인접한 두 수의 gcd가 모두 1이 되도록 만든다.

 

풀이

앞에서부터 보면서 인접한 두 수의 gcd가 2이상일 때 사이에 1을 넣는걸 반복한다.

 

소스코드

#include <stdio.h>
using namespace std;
typedef long long ll;
int gcd(int a,int b){
    if(a%b==0) return b;
    return gcd(b,a%b);
}
int main(){
    int n, k=0, a;
    int v[11000]={0};
    scanf("%d",&n);
    for(int i=0; i<n; ++i){
        scanf("%d",&a);
        if(i && gcd(v[k-1],a)>1) v[k++]=1;
        v[k++]=a;
    }
    printf("%d\n",k-n);
    for(int i=0; i<k; ++i) printf("%d ",v[i]);
}