题解：AT_pakencamp_2020_day1_k Gcd of Sum

xcb__fhuHGFgf56454 · 2026-07-25 16:59:51 · 题解

题目传送门

很明显可以猜到，最大公因数一定是 sumA 的因数。

另外我们注意到输出是单调不递增的，因此我们可以从大到小枚举 sumA 的因数。

那么我们该怎么求一个因数可以分出多少的区间呢？

注意到题目要求分为连续子序列（我不会告诉你我没看到连续导致我卡了一个小时），因此考虑前缀和。

我们分为的每个区间都要是 g 的倍数，我们可以统计有多少个位置的前缀和是 g 的倍数。这是因为如果 (0,L] 和 (0,R] 的和都是 g 的倍数，那么 (L,R] 也是 g 的倍数。

假设有 cnt 个位置的前缀和是 g 的倍数，这说明答案是 g 的 K 一定满足 1\le K\le cnt。因为我们从大到小枚举因数，因此只需要向前赋值到已经赋值过的地方就可以了。

:::info[代码]

#include<bits/stdc++.h>
#define int long long
#define il inline
#define fi first
#define se second
#define y1 Y1
#define For(a,b,c) for(int (a)=(b);(a)<=(c);(a)++)
#define For_(a,b,c) for(int (a)=(b);(a)>=(c);(a)--)
#define fr(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
#ifdef ONLINE_JUDGE
#define gc() getchar_unlocked()
#define pc(x) putchar_unlocked(x)
#else
#define gc() getchar()
#define pc(x) putchar(x)
#endif
using namespace std;using ull=unsigned long long;using i128=__int128;using db=double;using PII=pair<int,int>;const db eps=1e-9;
const int INF=0x3f3f3f3f3f3f3f3f,MOD=1000000007,MOD1=998244353,MOD2=1004535809,MOD3=469762049,G=3;
il void read(signed& x){x=0;int f=1;char ch=gc();while(!isdigit(ch)&&ch!=EOF)f=ch=='-'?-1:1,ch=gc();while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=gc();x=f==-1?-x:x;}
il void write(signed x){if(x<0) pc('-'),x=-x;char ch[10];int len=0;if(x==0) ch[len++]='0';while(x>0) ch[len++]=x%10+'0',x/=10;for(int i=len-1;i>=0;i--) pc(ch[i]);}
il void read(int& x){x=0;int f=1;char ch=gc();while(!isdigit(ch)&&ch!=EOF)f=ch=='-'?-1:1,ch=gc();while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=gc();x=f==-1?-x:x;}
il void write(int x){if(x<0) pc('-'),x=-x;char ch[20];int len=0;if(x==0) ch[len++]='0';while(x>0) ch[len++]=x%10+'0',x/=10;for(int i=len-1;i>=0;i--) pc(ch[i]);}
il void read(ull& x){x=0;char ch=gc();while(!isdigit(ch)&&ch!=EOF)ch=gc();while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=gc();}
il void write(ull x){char ch[21];int len=0;if(x==0) ch[len++]='0';while(x>0) ch[len++]=x%10+'0',x/=10;for(int i=len-1;i>=0;i--) pc(ch[i]);}
il void read(bool& x){char ch=gc();while(ch!='0'&&ch!='1'&&ch!=EOF)ch=gc();x=(ch=='1');};
il void write(bool x){putchar(x^48);}
il void read(i128& x){x=0;int f=1;char ch=gc();while(!isdigit(ch)&&ch!=EOF) f=ch=='-'?-1:1,ch=gc();while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc();x=f==-1?-x:x;}
il void write(i128 x){if(x<0) pc('-'),x=-x;char ch[40];int len=0;if(x==0) ch[len++]='0';while(x>0) ch[len++]=x%10+'0',x/=10;for(int i=len-1;i>=0;i--) pc(ch[i]);}
il void read(string& x){x="";char ch=gc();while((ch==' '||ch=='\t'||ch=='\n')&&ch!=EOF) ch=gc();while(ch!='\n'&&ch!='\t'&&ch!=' '&&ch!=EOF)x+=ch,ch=gc();}
il void readl(string& x){x="";char ch=gc();while(ch=='\n'&&ch!=EOF) ch=gc();while(ch!='\n'&&ch!=EOF) x+=ch,ch=gc();}
il void write(string x){for(char c:x) pc(c);}il void write(const char* s){while(*s) pc(*s++);}
il void read(char& x){x=gc();while((x==' '||x=='\n'||x=='\t')&&x!=EOF) x=gc();}
il void write(char ch){pc(ch);}il void end(){pc('\n');}il void end_(){pc(' ');}
template<typename T,typename... Args> il void read(T& x,Args&... args){read(x);read(args...);}
template<typename T,typename... Args> il void write(T x,Args... args){write(x);write(args...);}
//-------------------------------------我是分割线------------------------------------------------------------------------------
int n,a[2010],qzh[2010],suma,ans[2010];
vector<int>p; // suma 的所有因数
signed main(){
    read(n);
    For(i,1,n){
        read(a[i]);
        suma+=a[i];
        qzh[i]=qzh[i-1]+a[i];
    }
    for(int i=1;i*i<=suma;i++){
        if(suma%i==0){
            p.push_back(i);
            if(i*i!=suma) p.push_back(suma/i);
        }
    }
    sort(p.rbegin(),p.rend()); // 从大到小
    for(auto q:p){
        int cnt=0;
        For(i,1,n){
            if(qzh[i]%q==0){
                cnt++;
            }
        }
        For_(i,cnt,1){
            if(!ans[i]){
                ans[i]=q;
            }
            else break; //前面都填了
        }
    }
    For(i,1,n){
        write(ans[i]),end();
    }
    return !"I'm xcb";
}

:::