测试样例:
3
2 6 12
很多答案结果为3
其实为6
解题思路:
先排序。
因为该序列是等差数列的子序列。所以相邻两项的差一定是公差的倍数。
而如果要得到序最小,那么一定要使得公差最大。
所以要求出序列所有相邻两项差的最大公因数, 最大公因数即使最大公差。
过程:
①排序
②求出相邻两项之差 d1,d2, d3, d4;
③求出差的最大公因数d。
④d就是最大的公差
⑤项数n = (an-a1)/d+1
注意事项: 注意公差为0的情况
参考代码:
/*** ***/ #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const long MAXN = 100005; long arr[MAXN]; long N; long gcd(long x, long y){ return y==0?x:gcd(y, x%y); } int main(){ ios_base::sync_with_stdio(false); cin>>N; for(long i = 0;i < N;i++){ cin>>arr[i]; } sort(arr, arr+N); long maxd= arr[1]- arr[0]; if(maxd == 0){ cout<<N; return 0; } for(long i = 2;i < N;i++){ maxd = gcd(arr[i]- arr[i-1], maxd); } cout<<(arr[N-1]-arr[0])/maxd+1; return 0; }
0.0分
10 人评分
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:578 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:901 |
模拟计算器 (C语言代码)浏览:2299 |
简单的a+b (C语言代码)浏览:460 |
C语言训练-8除不尽的数 (C语言代码)浏览:1396 |
【魔板】 (C++代码)浏览:1157 |
1025题 初学者,求帮忙看下,不知道哪错了浏览:316 |
C语言程序设计教程(第三版)课后习题10.7 指针(C语言代码)浏览:538 |
C语言程序设计教程(第三版)课后习题11.1 (C++代码)浏览:681 |
C语言训练-求PI* (C语言代码)浏览:512 |