[题解]第十一届北航程序设计竞赛预赛—

题目描述

给一个长度为n(1<=n<=100000)的正整数列，分成尽量多的非空段，使得每一段的最大公约数相等。一个数的最大公约数是它本身。

解题思路

要求每一段子列的gcd相等，不妨设为d，可以知道d是所有数的最大公约数，即d=(a[1],a[2],……,a[n])。于是我们先求出d，然后从前往后扫描，记st=1，移动ed，计算d1=(a[st],……,s[ed])，直到d1==d，得到的区间[st,ed]就是一个符合题目要求的子列；记st=ed+1，重复上述操作，直至数列扫完。算法时间复杂度为O(n logx)，其中x表示数列的数的大小。

注：

1、由于gcd(a[i],……,a[j])=gcd(gcd(a[i],……,a[k]),gcd(a[k+1],……,a[j]))，(i<k<j)，所以计算多个数的gcd直接两两计算即可；计算子列的gcd直接在扫描时每多一个书就多一次求gcd即可。

2、按照上述算法可能出现最后一段的gcd不等于d的情况，可以看作最后一段不被单独分出来，而是跟前一段合并为一段的。注意到跟前面的一段合并后gcd一定等于d，因为d=(a[1],a[2],……,a[n])，最后一段的gcd记为ds只能是d的倍数，而前一段的gcd为d，所以合并后gcd一定为d。另外，所谓“前一段”是一定存在的，否则所有的最大公约数不可能为d。

附：c++代码

 1 #include <iostream>

 2 #include <cstdio>

 3

 4 using namespace std;

 5 #define MaxN 100020

 6

 7 int a[MaxN];

 8

 9 inline void Get_int(int &Ret)

10 {

11     char ch;

12     bool flag=false;

13     for(;ch=getchar(),ch<'0'||ch>'9';)

14         if(ch=='-')

15             flag=true;

16     for(Ret=ch-'0';ch=getchar(),ch>='0'&&ch<='9';Ret=Ret*10+ch-'0');

17     flag&&(Ret=-Ret);

18 }

19

20 inline int My_gcd(int a, int b)

21 {

22     int r;

23     if(a < b)

24         swap(a, b);

25     while(b)

26     {

27         r = a % b;

28         a = b;

29         b = r;

30     }

31     return a;

32 }

33

34 int main ()

35 {

36     int n, ans;

37     int x, tmp;

38     int i;

39     bool flag;

40     while(scanf("%d", &n) != EOF)

41     {

42         for(i = 1; i <= n; i++)

43         {

44             Get_int(a[i]);

45             if(i == 1)

46                 x = a[i];

47             else

48                 x = My_gcd(a[i], x);

49         }

50         if(n == 1)

51         {

52             printf("1\n");

53             continue;

54         }

55         //printf("%d\n", x);

56         ans = 0;

57         flag = false;

58         for(i = 1; i <= n; i++)

59         {

60             if(!flag)

61             {

62                 if(a[i] == x)

63                     ans++;

64                 else

65                 {

66                     tmp = a[i];

67                     flag = true;

68                 }

69             }

70             else

71             {

72                 tmp = My_gcd(a[i], tmp);

73                 if(tmp == x)

74                 {

75                     flag = false;

76                     ans++;

77                 }

78             }

79         }

80         printf("%d\n", ans);

81     }

82     return 0;

83 }

另一种思路

这是官方给出的题解，动归

最大公约数满足结合律，所以题目所说相等的gcd就是原数列的gcd，不妨设为d。

设f[i]为前i个数能分的最大段数，枚举最后一个段是[j+1,i]，则有gcdik=j+1ak=d，而f[i]=maxf[j]+1。如果j不存在，可以认为f[i]是不合法的部分，令f[i]=0即可。

不难证明满足条件的j是一段前缀区间，而且f[i]是单调的，所以最大的f[j]一定是尽量靠右的，可以直接找到这个j来对f[i]更新答案。

区间gcd可以预处理ST表得到，或者顺着推以每个点结尾的区间gcd即可，可以证明以每个点结尾的区间gcd的值个数是不超过logn个的，所以整体的复杂度是O(n(logn)^2)。

题目链接：https://biancheng.love/contest-ng/index.html#/29/problems

巴特西

[题解]第十一届北航程序设计竞赛预赛——D.最大公约数

最新文章

热门文章