1.最大公约数

这个题最重要的是要找到一个区间是1，找到之后就可以直接加次数就可以了

#include <bits/stdc++.h>using namespace std;main()
{long long n,i,j,a=0,b,ans=99999;cin>>n;long long s[n],dp[n][n];for(i=0;i<n;i++){cin>>s[i];if(s[i]==1) a=1;}if(a==1) {cout<<n-1;return 0;	}memset(dp,0,sizeof(dp));for(i=0;i<n;i++){dp[i][0]=s[i];dp[i][i]=s[i];}for(i=0;i<n;i++){for(j=i+1;j<n;j++){dp[i][j]=__gcd(dp[i][j-1],s[j]);}}for(i=0;i<n;i++){for(j=i;j<n;j++){
//			cout<<dp[i][j]<<" ";if(dp[i][j]==1){ans=min(ans,j-i);}}}cout<<ans+n-1;return 0;
}