网站建设中字样图片,教育行业网站制作,如何选择顺德网站建设,做网站图片处理问题[蓝桥杯 2022 国 A] 最大公约数
题目描述
给定一个数组#xff0c;每次操作可以选择数组中任意两个相邻的元素 x , y x, y x,y 并将其中的一个元素替换为 gcd ( x , y ) \gcd(x, y) gcd(x,y)#xff0c;其中 gcd ( x , y ) \gcd(x, y) gcd(x,y) 表示 x x x 和 y…[蓝桥杯 2022 国 A] 最大公约数
题目描述
给定一个数组每次操作可以选择数组中任意两个相邻的元素 x , y x, y x,y 并将其中的一个元素替换为 gcd ( x , y ) \gcd(x, y) gcd(x,y)其中 gcd ( x , y ) \gcd(x, y) gcd(x,y) 表示 x x x 和 y y y 的最大公约数。请问最少需要多少次操作才能让整个数组只含 1 1 1。
输入格式
输入的第一行包含一个整数 n n n表示数组长度。
第二行包含 n n n 个整数 a 1 , a 2 , … , a n a_1, a_2,\dots, a_n a1,a2,…,an相邻两个整数之间用一个空格分隔。
输出格式
输出一行包含一个整数表示最少操作次数。如果无论怎么操作都无法满足要求输出 − 1 -1 −1。
样例 #1
样例输入 #1
3
4 6 9样例输出 #1
4提示
【评测用例规模与约定】
对于 30 % 30\% 30% 的评测用例 n ≤ 500 n \leq 500 n≤500 a i ≤ 1000 a_i \leq 1000 ai≤1000对于 50 % 50\% 50% 的评测用例 n ≤ 5000 n \leq 5000 n≤5000 a i ≤ 1 0 6 a_i \leq 10^6 ai≤106对于所有评测用例 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105 1 ≤ a i ≤ 1 0 9 1 \leq a_i \leq 10^9 1≤ai≤109。
蓝桥杯 2022 国赛 A 组 D 题。
要点摘要
1、求连续区间的gcd等于1的最短长度;
2、全部的数的gcd不为1则输出-1;
3、dp数塔模型遇1即停。
4、__gcd(0,m)m;
5、答案最短长度剩余(n-1)个变1的操作次数-原数组1的个数
ll dp[30][N];
void solve()
{cinn;for(int i0;in;i){cinb[i];dp[0][i]b[i];m__gcd(m,b[i]);if(b[i]1)ans;}if(m1){cout-1;return;}for(int i1;in;i){for(int ji;jn;j){dp[i][j]__gcd(dp[i-1][j],dp[i-1][j-1]);if(dp[i][j]1){ki;goto out;}} }//coutk;out:coutkn-1-ans;
}一发过就很开森
