【代码源每日一题Div1】最大公约数「数学/枚举/环」

#131. 最大公约数

题目描述：

给你一个环，环上有n个正整数，你可以将环切成不相交的k段，每段包含若干个数字

对于一个切分方案，优美程度为每段数字和的最大公约数，你想使切分方案的优美程度最大，对于k=1,2,…,n输出答案

思路：

假设对于k，我们的答案是g，则需要满足n个数字分成的k段，每段数字的和都是g的倍数，则答案g一定是 ${\sum }_{i=1}^{n}ar[i]$的约数，我们可以枚举 ${\sum }_{i=1}^{n}ar[i]$的约数来求解

假设当前枚举的约数是x

先思考一下如果问的不是环，而是简单的数组，则我们可以搞一个前缀和pre，n个位置中pre[i]%x=0的数量计作是num,则对于k<=num的情况的答案都可以是x，因为有num段和为x的倍数的序列，可以通过合并相邻的%x=0的段来减少段数

所以我们维护一个ans的后缀最大值即可

void cal(int x){
	int cnt = 0;
	for(int i = 1; i <= n; ++i){
		if(pre[i]%x==0)++cnt;
	}
	ans[cnt] = max(ans[cnt], x);
}
for(int i = n; i >= 1; --i)ans[i] = max(ans[i], ans[i+1]);
for(int i = 1; i <= n; ++i)cout << ans[i]<<endl;
1
2
3
4
5
6
7
8
9

再思考一下怎么处理环的问题

假设当前枚举的因数是x

显然 $({\sum }_{i=1}^{n}ar[i])$%$x=0$，对于某个pre[i]%x，他在数组中出现的次数即为环上的某种分割方式下的段数，原因是，如果存在两个地方 pre[i]%x=pre[j]%x 则,区间 [i−1,j] 的和是 x 的倍数，由于 ${\sum }_{i=1}^{n}ar[i]$%$x=0$ ，那么剩下的 ${\sum }_{p=1}^{i-2}ar[p]+{\sum }_{p=j+1}^{n}ar[p]$一定也是 x 的倍数

所以我们取最大的pre[i]%x的数量即可

#include
using namespace std;
#define int long long
#define endl '\n'
#define io ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define m_p(a, b) make_pair(a, b)

typedef long long ll;
typedef pair<int, int> pii;

#define MAX 300050

int n, m, x;
int tr[MAX];
int pre[MAX];
int ans[MAX];

void fuck(ll x){
    map<int, int>mp;
    int cnt = 0;
    for(int i = 1; i <= n; ++i){
        ++mp[pre[i]%x];
        cnt = max(cnt, mp[pre[i]%x]);
    }
    ans[cnt] = max(ans[cnt], x);
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
        pre[i] = pre[i - 1] + tr[i];
    }
    for(int i = 1; i <= sqrt(pre[n]); ++i){
        if(pre[n]%i == 0){
            fuck(i);
            fuck(pre[n]/i);
        }
    }
    for(int i = n; i >= 1; --i)ans[i] = max(ans[i], ans[i+1]);
    for(int i = 1; i <= n; ++i)cout << ans[i]<<endl;
}

signed main(){
    io;
    work();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49