Submission #1358237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1358237		Newtonabc	Gingerbread (BOI25_gcd)	C++20	100 / 100	217 ms	86508 KiB

Main

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
ll a[N],n;
bool ok;
void f(int i,ll lt,ll ac){
    if(ok) return;
    if(i==n){
        if(ac==-1) ac=a[i]+lt;
        else ac=__gcd(ac,a[i]+lt);
        if(ac==1) ok=true;
        return;
    }
    for(int j=0;j<=lt;j++){
        a[i]+=j;
        ll nxt;
        if(ac==-1) nxt=a[i];
        else nxt=__gcd(ac,a[i]);
        if(nxt==1){
            ok=1;
            return;
        }
        f(i+1,lt-j,nxt);
        if(ok) return;
        a[i]-=j;
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(ll i=0;i<=1e7;i++){
        f(1,i,-1);
        if(ok){
            cout<<i;
            return 0;
        }
    }
}

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 34 / 34
• Subtask 4: 11 / 11
• Subtask 5: 38 / 38