Educational Codeforces Round 11——A. Co-prime Array(map+vector)
1 second
256 megabytes
standard input
standard output
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 109 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 ai (1 ≤ ai ≤ 109) — 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 aj — 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 kelements to it.
If there are multiple answers you can print any one of them.
3
2 7 28
1
2 7 9 28
给你一个序列在不改变原来相对顺序的情况下插入最少个数使得该序列相邻数均为互质,只要插入的个数最少,答案可以不唯一。本来以为会WA,没想到过了。
代码:
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
inline int gcd(const int &a,const int &b)
{
return b?gcd(b,a%b):a;
}
int main (void)
{
int n,i,j,ans,t;
while (cin>>n)
{
vector<int>vec;
map<int,int>pos;
for (i=0; i<n; i++)
{
cin>>t;
vec.push_back(t);
}
for (i=0; i<n-1; i++)
{
if(gcd(vec[i],vec[i+1])!=1)
{
for (j=2; j<=100000000; j++)
{
if(gcd(vec[i],j)==1&&gcd(vec[i+1],j)==1)//map记录每个位置是否要放入和放入的值
{
pos[i]=j;
break;
}
}
}
}
cout<<pos.size()<<endl;
for (i=0; i<n; i++)
{
if(pos.find(i)!=pos.end())
cout<<vec[i]<<" "<<pos[i];
else
cout<<vec[i];
if(i==n-1)
cout<<endl;
else
cout<<" ";
}
}
return 0;
}
最新文章
- Python多进程(2)——mmap模块与mmap对象
- SQL SERVER 中的提示
- LeetCode-Sort Colors
- centos7.2环境elasticsearch-5.0.1+kibana-5.0.1+zookeeper3.4.6+kafka_2.9.2-0.8.2.1部署详解
- Visio 2007中进行数据库建模时如何显示字段类型以及概念名称
- 七个结构模式之桥接模式(Bridge Pattern)
- 点击某个按钮弹出 photoswip
- 深入学习golang(3)—类型方法
- cocos2d-x之物理按键初试
- java利用过滤器实现编码的转换,内容输出的替换
- spring初探1
- QT-【转】2D编程
- PHP字符串替换函数strtr()
- linux中的openoffice服务终止运行
- 利用jquery实现百度新闻导航菜单滑动动画
- android--手机桌面添加网址链接图标(解决方式)
- Qt文字编码
- shell中$(( )) 与 $( ) 还有${ }的区别
- XBMC源代码分析 6:视频播放器(dvdplayer)-文件头(以ffmpeg为例)
- 从javascript发展说到vue