算法总结—最大公约数2

LRRabcd · 2024-10-08 18:56:09 · 算法·理论

等差数列

由于这道题要求项数最少，所以这道题的公差就要越大，所以这道题的公差 d 就是排好序后的 \gcd(a_i-a_{i-1}),2\leq i\leq n。

知道了公差，项数的求解公式就是 \frac{(a_n-a_1)}{d}+1。

注意点

这道题的公差可能为 0，如果排好序后 a_1=a_n 就意味着公差为 0 直接输出 n 即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100005];
int diff[100005];
int gcd(int x,int y){
    if(y==0){
        return x;
    }
    return gcd(y,x%y);
}
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    if(a[1]==a[n]){
        cout<<n;
        return 0;
    }
    for(int i=1;i<=n;i++){
        if(i==1){
            continue;
        }
        diff[i]=a[i]-a[i-1];
    }
    int Gcd=0;
    for(int i=2;i<=n;i++){
        Gcd=gcd(Gcd,diff[i]);
    }
    cout<<(a[n]-a[1])/Gcd+1;
    return 0;
}

Xor with Gcd

这道题运用的是 \gcd 根相损减数：

\gcd(a,b)=\gcd(b-a,b)

同样运用这题中就是：

\gcd(i,n)=\gcd(n-i,n)

所以 \gcd(1,n),\gcd(2,n),...,\gcd(n-1,n) 这个序列基本上是回文的。又根据异或的规律相同的数相异或结果为 0 ，所以这个序列中的大部份都被消掉了，接下来份类讨论：

## 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        if(n%2){
            cout<<n<<"\n";
        }else{
            cout<<((n/2)^n)<<"\n";
        }
    }
    return 0;
}

消消乐

这道题中最大的两个数一定不会被消除。

我们设 n=10 (每个数均不相同)且 \gcd(a_{10},a_9)=a_1，则 a_8 一定不能能被删除，所以这道题只需要判断从大到小排序后的每一个 \gcd(a_i,a_{i+1}) 是否等于 a_{i+2} 即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int gcd(int x,int y){
    if(y==0){
        return x;
    }
    return gcd(y,x%y);
}
int a[1000005];
void work(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    cout<<"Yes\n";
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        work();
    }
    return 0;
}

椰子

10 分 \text{(Subtask\ 1)}

直接暴力，时间复杂度 O(n^4)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int gcd(int x,int y){
    if(y==0){
        return x;
    }
    return gcd(y,x%y);
}
int a[500005];
set<int>st;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        int t;
        int pos=0;
        for(int j=1;j<=n;j++){
            if(a[j]==i){
                t=a[j];
                pos=j;
                a[j]=1;
                break;
            }
        }
        st.clear();
        for(int l=1;l<=n;l++){
            for(int r=l;r<=n;r++){
                int Gcd=0;
                for(int j=l;j<=r;j++){
                    Gcd=gcd(Gcd,a[j]);
                }
                st.insert(Gcd);
            }
        }
        cout<<st.size()<<" "; 
        a[pos]=t;
    }
    return 0;
}

30 分 \text{(Subtask\ 2)}

由于 r 是一只再往后走，所以不用每枚举一对 (l,r) 就计算一次，这样有砍掉一层循环，时间复杂度 O(n^3)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int gcd(int x,int y){
    if(y==0){
        return x;
    }
    return gcd(y,x%y);
}
int a[500005];
set<int>st;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        int t;
        int pos=0;
        for(int j=1;j<=n;j++){
            if(a[j]==i){
                t=a[j];
                pos=j;
                a[j]=1;
                break;
            }
        }
        st.clear();
        for(int l=1;l<=n;l++){
            int Gcd=0;
            for(int r=l;r<=n;r++){
                Gcd=gcd(Gcd,a[r]);
                st.insert(Gcd);
            }
        }
        cout<<st.size()<<" "; 
        a[pos]=t;
    }
    return 0;
}

60 分 \text{(Subtask\ 3)}

由于 \gcd 越往后找，就会越小，所以只要有一个 \gcd 重复了，就直接 break。时间复杂度 \leq O(n^3)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int gcd(int x,int y){
    if(y==0){
        return x;
    }
    return gcd(y,x%y);
}
int a[500005];
unordered_map<int,int>mp;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        int t;
        int pos=0;
        for(int j=1;j<=n;j++){
            if(a[j]==i){
                t=a[j];
                pos=j;
                a[j]=1;
                break;
            }
        }
        mp.clear();
        int cnt=0;
        for(int l=1;l<=n;l++){
            int Gcd=0;
            for(int r=l;r<=n;r++){
                Gcd=gcd(Gcd,a[r]);
                if(mp[Gcd]==0){
                    cnt++;
                    mp[Gcd]=1;
                }else{
                    break;
                }
            }
        }
        cout<<cnt<<" "; 
        a[pos]=t;
    }
    return 0;
}

80 分 \text{(Subtask\ 4)}

特殊性质 a_i=i：输出 1 个 n，n-1 个 n-1 即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int gcd(int x,int y){
    if(y==0){
        return x;
    }
    return gcd(y,x%y);
}
int a[500005];
unordered_map<int,int>mp;
bool check(int a[],int n){
    for(int i=1;i<=n;i++){
        if(a[i]!=i){
            return 0;
        }
    } 
    return 1;
}
int ans[500005];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        ans[i]=n;
        if(i>1){
            ans[i]--;
        }
    }
    if(check(a,n)){
        for(int i=1;i<=n;i++){
            cout<<ans[i]<<" ";
        }
        return 0;
    }
    for(int i=1;i<=n;i++){
        int t;
        int pos=0;
        for(int j=1;j<=n;j++){
            if(a[j]==i){
                t=a[j];
                pos=j;
                a[j]=1;
                break;
            }
        }
        mp.clear();
        int cnt=0;
        for(int l=1;l<=n;l++){
            int Gcd=0;
            for(int r=l;r<=n;r++){
                Gcd=gcd(Gcd,a[r]);
                if(mp[Gcd]==0){
                    cnt++;
                    mp[Gcd]=1;
                }else{
                    break;
                }
            }
        }
        cout<<cnt<<" "; 
        a[pos]=t;
    }
    return 0;
}

100 分 \text{(Subtask\ 5)}

这种 100 分的解法是假解，是因为数据过水才过的。

一个答案要么是 n 要么是 n-1，我们可以求一个数相邻的的几个数，求他们的 \gcd 在统计即可，为什么是相邻三个呢，~~因为数据太弱了。~~

#include<bits/stdc++.h>
using namespace std;
int a[500005];
bool vis[500005];
int gcd(int x,int y){
    if(y==0){
        return x;
    }
    return gcd(y,x%y);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    vis[1]=1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i==1){
            continue;
        }
        int Gcd=gcd(a[i-1],a[i]);
        if(Gcd!=a[i-1]&&Gcd!=a[i]){
            vis[Gcd]=1;
        }
        for(int j=2;j<=3;j++){
            Gcd=gcd(Gcd,a[i-j]);
            if(Gcd!=a[i-j]){
                vis[Gcd]=1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(vis[i]){
            cout<<n<<" ";
        }else{
            cout<<n-1<<" ";
        }
    }
    return 0;
}