（CF1367E）《》

Senior_Young · 2026-05-04 17:12:59 · 题解

Preface

好吧这题我早就做过了，现在又做到了，结果不会（？）

更好的阅读体验

::::info[关于下文中的“重复段”和“极大重复段”]

• “重复段”是指一个段或整条项链的某个子段，满足这个段由多个该子段拼接而成。

• “极大重复段”是指该重复段无法分出更小的重复段。

Problem

见洛谷题面和原题面。

Solution

我们发现极大重复段的段长一定是 k 的因数。

当然极大重复段的段长也一定是项链长度（设其为 i）的因数。显然项链长度也是可以枚举的。

所以我们可以设整条项链的某个重复段的长度 d 为 \gcd(k,i)，然后计算这个重复段的长度合不合法。

具体的，我们尽可能多的往每个重复段里平均分配珠子，也就是对于某种有 x 个的珠子，往每个重复段里分配 \lfloor x/\frac{i}{d} \rfloor 个珠子，然后计算珠子的数量能否凑出 d 个。

至于为什么我们设 d 为最大的合法的 d（即 \gcd(k,i)），可以看下面的解释。

::::info[解释]

• 对于某种有 x 个的珠子，得到分配的珠子数量是 \lfloor x/\frac{i}{d} \rfloor \times \frac{i}{d} 个；
• 换言之，没得到分配的珠子数量是 ( x \bmod \frac{i}{d} ) 个；
• 设 i/\gcd(k,i)=y，因为所有可能的 d 都是 \gcd(k,i) 的因数，所以所有可能的 i/d 都是 y 的倍数。
• 可以证明对于任何合法的 d，都有 x \bmod \frac{i}{d} \ge x \bmod y。 :::info[关于上述命题的严谨证明] 我们相当于要证明：若 a 是 b 的倍数，则对任意正整数 c，都有 (c \bmod a \ge c \bmod b)。

设 a = m b，其中 m 为正整数。对任意正整数 c，由带余除法可得：

这里 r_a = c \bmod a，r_b = c \bmod b。

将 a = m b 代入第一个等式：

Code

::::success[代码在这里喵]

#include<bits/stdc++.h>
using namespace std;
int n,K;
string s;
int cnt[26];
void man(){
    memset(cnt,0,sizeof cnt);
    cin>>n>>K;
    cin>>s;
    for(int i=1;i<=n;i++){
        int k=s[i-1]-'a';
        cnt[k]++;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        int d=__gcd(i,K);
        int res=0;
        for(int j=0;j<26;j++){
            res+=cnt[j]/(i/d);
        }
        if(res>=d) ans=i;
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;cin>>T;
    while(T--) man();
    return 0;
}

::::

Postscript

写题解不易喵，点个赞好不好喵～