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是互质数。