几个关于素数的重要基础公式

• $gcd(a,b)=gcd(a,a-b)(a>b)$证明
• $gcd(a,b)=gcd(a,a+b)(a>b)$ 证明同上
• $gcd(a,a+1)=1(a>=1)$
• 证明的话就相等于在已知$gcd(a,a+b)=gcd(a,b)时把b看成1 就可以知道gcd(a,1)=1=gcd(a,a+1)$证毕

B. Nastia and a Good Array

题意:每次可以选数组中任意两个不同的数 使得 两个数变成新的两个数 但是新的两个数的最小值一定是 原来两个数的最小值 最后在不超过n次的操作下使得整个数组的任意两个数都是互素的

思路:直接找到数组中的最小值的位置 使得数组变成以该位置为起点的一个类似波谷的序列 从该位置向两边每次递增即可 由于 每次操作一定包含该数 且每次只+1 最多操作n-1次 就使得所有相邻的数都只相差1 即相邻位置是互素的
AC代码

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
        return b?a:gcd(b,a%b);
}
int main()
{
       // freopen("test.in","r",stdin);
        int t;cin>>t;
        while(t--)
        {
                int n;cin>>n;
                vector<int>a(n+1);
                for(int i=1;i<=n;i++)cin>>a[i];
                int pos=min_element(a.begin()+1,a.end())-a.begin();
                cout<<n-1<<endl;
                for(int i=1;i<=n;i++)
                {
                        if(i!=pos)
                        {
                                if(i<pos)cout<<i<<' '<<pos<<' '<<a[pos]+abs(pos-i)<<' '<<a[pos]<<endl;
                                else cout<<pos<<' '<<i<<' '<<a[pos]<<' '<<a[pos]+abs(pos-i)<<endl;
                        }
                }
        }
        return 0;
}

时间复杂度$O(n)$