原题链接
题意
给一串数,要把任意两个相邻的数的最大公约数=1
每次可以进行一个操作:
取下标为i, j的数,和任意二数x,y,且min(ai,aj)=min(x,y)
满足上述条件,即可使ai=x,aj=y
限制条件:操作次数 <= n
思路
找到数列最小值,操作完是最小值不变,其余数大小=最小值+(每个数与最小数下标差值)
换句话说:以最小值为中心,两边依次递增、
附:每次以最小值操作可以保证不越界,而且具有稳定性,不会出现操作者的值小于最小值
代码
#include <iostream> #include<algorithm> //找到最小的, 后面都-1 using namespace std; typedef long long ll; const int N = 1e5 + 10; ll a[N]; int gcd(int a, int b) { return b == 0? a: gcd(b, a%b); } int main() { int t; cin >> t; while(t --) { int n; cin >> n; for(int i = 1; i <= n; i ++) cin >> a[i]; a[0] = 0x3f3f3f3f; int minn = 0; for(int i=1; i <= n; i ++) { if(a[i] < a[minn]) minn = i; } ll x1 = a[minn], x2 = a[minn]; cout << n-1 << endl; for(int i = minn; i < n; i ++) { cout << minn << ' '<< i+1 <<' ' << a[minn] << ' '<< 1+x1<<endl; x1 ++;//这里, 从最小到后面 } for(int i = minn; i > 1; i --) { cout << i-1 << ' '<< minn <<' ' << x2+1 << ' '<< a[minn]<<endl; x2 ++;//这里, 从最小到前面 } } return 0; }