题解：AT_pakencamp_2020_day1_k Gcd of Sum

· · 题解

把连续的子序列看成子序列的说是。

记 d = \gcd(C_1,C_2,\cdots,C_K)。容易发现 \forall i\in [1,K],\ d\mid C_i。

将 C_i 求和，得到一个有点弱的限制：d\mid\sum_{i=1}^N A_i。

所以 d 一定是 \sum_{i=1}^N A_i 的因数，而这样的 d 一共只有 \tau\left(\sum_{i=1}^N A_i\right)=O\left(\sqrt{2\times10^{12}}\right)=O\left(10^6\right) 个，同时严重不满，于是考虑枚举 d。

对于一个二元组 (K,d)，记 p(K,d) 表示该二元组是否满足条件。我们可以合并相邻两个 C_i，从而减少 K 的值。也就是说，存在布尔关系的传递式 p(K,d) \longmapsto p(K-1,d)。

于是，我们只需要对于每一个 d，求出满足条件的最大的 K，然后算一遍后缀最大值即可。

由于这里是连续子序列（即子串），所以可以做一遍前缀和然后差分得到子串和。

记 S_n = \sum_{i=1}^nA_i 则 \sum_{i=l}^rA_i=S_r-S_{l-1}。同时记划分子串的区间分别为 (L_i,R_i]，则限制条件 d\mid C_i 就变成了 d\mid (S_{R_i}-S_{L_i})\Longrightarrow S_{R_i}\equiv S_{L_i}\pmod d。

因为有 L_1=0（第一个子串从头开始），所以 S_{R_1}\equiv S_{L_1}=0\pmod d。又因为 L_{i-1}=R_i，所以传递得到 S_{R_i}\equiv 0\pmod d，从而 K 的最大值为 S 数组中模 d 为 0 的个数。

时间复杂度：O\left(n\times \tau\left(\sum_{i=1}^NA_i\right)\right)。

引用一下 035966_L3 写的文章里面的这个图片：

知道当 n\lt 10^{13} 时，d(n)\lt10752。于是我们确保了我们复杂度的正确性。

:::success[代码]

ATcoder 提交记录。

/*

Start Code At 2026/7/25 7:59:11 .

Code by Bestart (luogu uid : 1062290) .

*/

#include <bits/stdc++.h>
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , fread_cnt , stdin) , p1 == p2) ? EOF : *p1 ++)

using namespace std ;

using db    = double ;
using i128  = __int128 ;
using ll    = long long ;
using ldb   = long double ;
using uint  = unsigned int ;
using ui128 = unsigned __int128 ;
using ull   = unsigned long long ;

#define inline
//#define int long long

mt19937 rnd( chrono :: system_clock :: now() .time_since_epoch() .count() ) ;

const uint fread_cnt = 1 << 20 | 10 ;
const uint mod = 998244353 ;
const uint MN = 2e3 + 10 ;
const int inf = 1e9 + 7 ;
//const ll inf = 1e18 ;

char buf[fread_cnt] , *p1 = buf , *p2 = buf ;

template <typename T = int>
inline T read()
{
    bool f = 0 ;  T x = 0 ;  char ch = gc() ;

    while(ch < '0' || ch > '9')  f ^= ch == '-' , ch = gc() ;
    while(ch >= '0' && ch <= '9')  x = (x << 3) + (x << 1) + (ch ^ 48) , ch = gc() ;

    return f ? -x : x ;
}

uint n , a[MN] , cnt ;
ull s[MN] , p[MN] , b[MN] , res[MN] ;

inline void work (ull x) 
{
    for(ull i = 1 ; i*i <= x ; ++ i) 
    {
        if(x % i == 0) 
        {
            p[++ cnt] = i ;
            if(x != i*i)  p[++ cnt] = x/i ;
        }
    }
}

inline bool solve()
{

    cin >> n ;
    for(uint i = 1 ; i <= n ; ++ i)  cin >> a[i] , s[i] = s[i-1]+a[i] ;
    work(s[n]) ;
    for(uint i = 1 ; i <= cnt ; ++ i) 
    {
        uint tot = 0 ;
        for(uint j = 1 ; j <= n ; ++ j)  tot += s[j]%p[i]==0 ;
        res[tot] = max(res[tot] , p[i]) ;
    }
    for(uint i = n ; i >= 1 ; -- i)  res[i] = max(res[i] , res[i+1]) ;
    for(uint i = 1 ; i <= n ; ++ i)  cout << res[i] << '\n' ;

    return 0 ;
}

signed main()
{
//  freopen("aggravate.in" , "r" , stdin) ;
//  freopen("aggravate.out" , "w" , stdout) ;

    cin.tie(0) -> sync_with_stdio(0) ;

//  system("fc aggravate.out aggravate3.ans") ;

//  int t = 1 ;   cin >> t ;   while(t --)  solve() ;

//  while(!solve()) ;

    solve() ;

    return 0 ;
}

:::

:::info[短小精悍版]

#include <bits/stdc++.h>
using namespace std ;
const int MN = 2e3 + 10 ;
int n , a[MN] , cnt ;
long long s[MN] , p[MN] , b[MN] , res[MN] ;
signed main() {
    cin.tie(0) -> sync_with_stdio(0) ;
    cin >> n ;
    for(int i = 1 ; i <= n ; ++ i)  cin >> a[i] , s[i] = s[i-1]+a[i] ;
    for(long long i = 1 ; i*i <= s[n] ; ++ i)  if(s[n] % i == 0) {
        p[++ cnt] = i ;
        if(s[n] != i*i)  p[++ cnt] = s[n]/i ;
    }
    for(int i = 1 ; i <= cnt ; ++ i) {
        int tot = 0 ;
        for(int j = 1 ; j <= n ; ++ j)  tot += s[j]%p[i]==0 ;
        res[tot] = max(res[tot] , p[i]) ;
    }
    for(int i = n ; i >= 1 ; -- i)  res[i] = max(res[i] , res[i+1]) ;
    for(int i = 1 ; i <= n ; ++ i)  cout << res[i] << '\n' ;
    return 0 ;
}

:::