[第十届蓝桥杯省赛C++B组]等差数列

来源： 第十届蓝桥杯省赛C++B组

算法标签: 数论最大公约数

题目描述

数学老师给小明出了一道等差数列求和的题目。

但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。

现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？

输入格式

输入的第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN。(注意 A1∼AN 并不一定是按等差数
列中的顺序给出)

输出格式

输出一个整数表示答案。

数据范围

2≤N≤100000,
0≤Ai≤109

输入样例：

5
2 6 4 10 20

输出样例：

10

样例解释

包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、18、20。

思路

已知给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项
该数列为等差数列，求等差数列最短。
我们已知等差数列求N公式为(a(n)-a(0))/d+1，即等差数列 队尾减队头的差 除以 公差 +1；
由此我们知道，本题根本不需要其余的队列数字，现在的问题转为，如何使得队伍从小到大排序
以及为(a(n)-a(0))/d+1如何才能最短。

我们可以轻松的通过sort函数排序。
而使得 (a(n)-a(0))/d+1最小则需要使得 公差最大。

由此，最后一步，我们只需要通过辗转相除法求得最大d，即可通过等差公式求得答案。

C++ 代码

gcd

#include<iostream>
#include<algorithm>

using namespace std;
const int N=1e5+10;
int a[N];

int gcd(int a,int b)//辗转相除法 在两个数中求得最大公约数，当一方为0时，返回另一方。
{
    return b?gcd(b,a%b):a;
}

int main()  
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    
    sort(a,a+n);//回复等差数列正常排序
    
    int d=0;
    for(int i=1;i<n;i++)d=gcd(d,a[i]-a[0]);//求得数列中的最大公约数，又因为辗转相除，所以gcd(a,b)中a,b任意一个为零时，可以返回另一个数，再和下一个数求最大公约数。
    
    if(d)cout<<(a[n-1]-a[0])/d+1;//特判d为0！即有常数个，否则出现K/d时d==0逻辑错误Float Point Exception   
    else cout<<n;
    
    return 0;
}

枚举

注意

数据过到如下大小出现TML，且存在4 2 5 7 10出问题的情况，但是骗分差不多够了。

100000 510735260 430427260 325696180 181874000 301759672 306932452 305279052 55941608 280950452 184132072 751002624 577721580 334194656 113777540 379200204 242109724 150227924 199239424 11427356 855625052 575553264 979653672 782662872 138044728 533084504 320962732 196466436 253485116 129664352 138531300 32973520 535413436 885268152 699714156 697300192 801516356 880152060 685844492 630937440 146949468 268181480 811805228 629737544 123986104 599182712 301155000 515785216 565835996 917249632 924118328 676542936 998393780 374343932 282995944 395190944 862531540 346344784 241046824 209518848 849805084 5361740 708467728 666391060 563143316 316559964 210354996 935659060 8961428 828556532 836289720 103290260 269159348 37900652 666669776 660226240 97772628 679939492 518728268 243286000 552372596 587448296 377414532 196041276 148276912 337147156 607572536 386980632 778921464 893185576 106644300 310853372 656413972 247121888 790414956 321907532 985209096 798653612 740647616 285154812 45785008 336202356 884724892 344034748 718874700 183749428 499879508 583659648 883340760 7260788 339835112 18168504 606537980 210047936 996428596 649540552 550752264 811980016 365954108 17426836 114977436 164347960 816661500 965680080 816637880 87190868 924226980 421461108 263929880 215234888 245161428 867515360 806519072 319526636 617837788 261511192 335318968 405843564 863792848 143226956 955452620 526173292 301443164 686321616 915256104 398837872 664543976 60396340 328105420 515114408 90039440 410175472 551021532 177041348 23742824 705557744 690752728 546798276 86789328 501471496 491995152 46044828 261171064 466792612 865895028 586045268 234839488 628428996 401757304 97744284 187429424 476396504 577315316 574173856 332470396 59016932 989125292 482594392 525681996 991005444 399447268 228759700 570512756 761286772 934600884 355065288 906134060 560625424 725252100 260396328 433790748 503356372 726244140 495188576 769426224 948848468 445525164 819656516 831749956 600401504 990755072 884762684 16...

如果我们要保证正确性，则需要加check，但明显复杂度上天。
如果我们要压缩时间而不用gcd，应该还是数论的方向走。
本次仅为班级作业而言，我就不做过多强求。

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int cnt; int n;
int stepNum;

void check(int k)
{
	int step = 0, num = a[0];
	while (num < a[n - 1])//小于等差数列最大值
		step++, num += k;//项+1，数量加等差

	if (num == a[n - 1])b[cnt++] = step, stepNum++;//如果最后一项相等，则表明正确
}

int main()
{
	scanf("%d",&n);
	for (int i = 0; i < n; i++)scanf("%d",&a[i]);
	sort(a, a + n);
	

    int min_a_d=a[1]-a[0];
    for(int i=2;i<n;i++)
        min_a_d=min(min_a_d,a[i]-a[i-1]);//找最小公差
    
	for (int i = 1; i <= min_a_d; i++)check(i);//判断是否存在比最小公差小但是符合条件的情况

	sort(b, b + stepNum);
	
	printf("%d",b[0]+1);//输出多个情况中项最少的那一类
	return 0;
}