B. Nastia and a Good Array

B. Nastia and a Good Array

B. Nastia and a Good Array
B. Nastia and a Good Array
题目大意:
给定一个长度为n的序列,要求对每个a[i], a[i + 1] 进行变化为a,b使得gcd(a,b) == 1,且min(a[i],a[i+1])==min(a,b)。要求操作次数最多为n次。
思路:
一开始我写了一个质数筛,然后依次遍历整个数组,利用二分查找质数,结果小数据跑过了,大数据拉胯。。。
后来hz聚聚给出了互质的性质两个连续的自然数一定互质,所以我们只要进行小于n次操作改变序列即可,这里我们找到最小值,从该点开始左右两侧依次变为最小值加1,2,3…

#include<iostream>
#include<stack>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<cmath>
#include<queue>
using namespace std;

typedef long long ll;
const int p = 1e9 + 7;
typedef pair<int, int> pii;
const int N = 1e6+10;
map<ll, int>mp;

ll a[N];
ll gcd(ll a, ll b) {
	return b ? gcd(b, a % b) : a;
}
int main() {
	int t;
	cin >> t;

	while (t --)
	{
		
		ll n;
		cin >> n;
		ll hh = 0x3f3f3f3f;
		int pos = 0;
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
			if (a[i] < hh) {
				hh = a[i];
				pos = i;
			}
		}
		int flag = 0;
		for (int i = 1; i < n; i++) {
			if (gcd(a[i], a[i + 1]) != 1) {
				flag = 1;
				break;
			}
		}
		if (!flag) {
			puts("0");
			continue;
		}

		else
		cout << n - 1 << endl;
		int h = 1;
		for (int i = pos - 1; i >= 1; i--,h++) {
			cout << pos << ' ' << i << ' ' << a[pos] << ' ' << a[pos] + h << endl;
		}
		int x = 1;
		for (int i = pos + 1; i <= n; i++, x++) {
			cout << pos << ' ' << i << ' ' << a[pos] << ' ' << a[pos] + x << endl;
		}

		
	}
	

}

还有一些规律

(1)两个不相同的质数一定是互质数。例如,19和13是互质数。

(2)两个连续的自然数一定是互质数。例如,14和15是互质数。

(3)相邻的两个奇数一定是互质数。例如,91和93是互质数

(4)1和其它所有自然数一定是互质数。例如,1和4,1和13等。

(5)两个数中较大数为质数,这两个数一定是互质数。例如16和97是互质数。

(6)两个数中的较小一个是质数,较大数是合数且不是较小数的倍数,这两个数一定是互质数。例如,7和54是互质数。

(7)较大数比较小数的2倍多1或少1,这两个数一定是互质数,例如,13和27是互质数,13和25是互质数。

上一篇:Codeforces Round #720 (Div. 2) A. Nastia and Nearly Good Numbers


下一篇:B. Nastia and a Good Array(构造)