303403: CF660A. Co-prime Array

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Co-prime Array

题意翻译

### 题目描述 ### 给你一个n个元素的数组,你必须尽可能少的添加元素使得该序列成为一个co-prime数组。 每次可以插入任何正整数不大于10^9在数组的任意位置。 如果一个数组的任意两个相邻的数是互质的,那么这个数组就是co-prime。 ### 输入输出格式 #### 输入格式: 第一行 n (1≤n≤1000) 第二行 ai的描述 (1≤ai≤10^9) #### 输出格式: 第一行输出k的值---k为添加到数组a中使其成为co-prime数组的最少添加元素个数 第二行应该包含n+k个整数a[i]的输出 如果有多个答案,输出任意一个就行

题目描述

You are given an array of $ n $ elements, you must make it a co-prime array in as few moves as possible. In each move you can insert any positive integral number you want not greater than $ 10^{9} $ in any place in the array. An array is co-prime if any two adjacent numbers of it are co-prime. In the number theory, two integers $ a $ and $ b $ are said to be co-prime if the only positive integer that divides both of them is $ 1 $ .

输入输出格式

输入格式


The first line contains integer $ n $ ( $ 1<=n<=1000 $ ) — the number of elements in the given array. The second line contains $ n $ integers $ a_{i} $ ( $ 1<=a_{i}<=10^{9} $ ) — the elements of the array $ a $ .

输出格式


Print integer $ k $ on the first line — the least number of elements needed to add to the array $ a $ to make it co-prime. The second line should contain $ n+k $ integers $ a_{j} $ — the elements of the array $ a $ after adding $ k $ elements to it. Note that the new array should be co-prime, so any two adjacent values should be co-prime. Also the new array should be got from the original array $ a $ by adding $ k $ elements to it. If there are multiple answers you can print any one of them.

输入输出样例

输入样例 #1

3
2 7 28

输出样例 #1

1
2 7 9 28

Input

题意翻译

### 题目描述 ### 给你一个n个元素的数组,你必须尽可能少的添加元素使得该序列成为一个co-prime数组。 每次可以插入任何正整数不大于10^9在数组的任意位置。 如果一个数组的任意两个相邻的数是互质的,那么这个数组就是co-prime。 ### 输入输出格式 #### 输入格式: 第一行 n (1≤n≤1000) 第二行 ai的描述 (1≤ai≤10^9) #### 输出格式: 第一行输出k的值---k为添加到数组a中使其成为co-prime数组的最少添加元素个数 第二行应该包含n+k个整数a[i]的输出 如果有多个答案,输出任意一个就行

加入题单

上一题 下一题 算法标签: