题解归档 - cf1202F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf1202F
• 本地来源：problems/cf1202F/idea.md
• 题目链接：https://codeforces.com/contest/1202/problem/F
• 原始标题：CF1202F — You Are Given Some Letters...

思路

CF1202F — You Are Given Some Letters...

题意

给定 a 个 A、b 个 B，在所有长度为 n=a+b 的排列中，统计最小周期（period）的不同取值个数。

周期 k：最小正整数使 s_i = s_{i mod k}（0-indexed）。

做法

设 g = n / k（整除）为「完整周期块」个数，周期模板长度为 k，其中 cnt_a + cnt_b = k 为模板内 A/B 个数。

完整块贡献 cnt_a * g 个 A、cnt_b * g 个 B；余下 n - g*k 位由模板前缀填充。可构造当且仅当：

• a >= g 且 b >= g（余部非负且可放入模板）
• 存在整数 cnt_a, cnt_b 满足
  ceil(a/(g+1)) <= cnt_a <= floor(a/g)，
  ceil(b/(g+1)) <= cnt_b <= floor(b/g)，
  且 cnt_a + cnt_b = k

记 a_low, a_high, b_low, b_high 为上述上下界。固定 g 时所有合法 k 落在
[max(l, a_low+b_low), min(r, a_high+b_high)]，其中 l = n/(g+1)+1 型区间左端、r = n/g 为同 g 的最大 period。

按 g 分段扫：O(sqrt n)。参考 Educational Round 70 官方题解（PikMike 代码）。

实现要点

• 用 while(l<=n)，g=n/l；若 a<g or b<g 则 l=n/g+1 跳过。
• 答案累加 max(0, min(r,a_high+b_high)-max(l,a_low+b_low)+1)。
• a,b 可达 1e9，全程 long long。

本地验证

• 样例 2 4 -> 4，5 3 -> 5 通过。
• Python 复现快解/暴力逻辑 5000 组一致；Kali stress.py 多轮因 SSH 偶发中断，已跑通 100+ 组无 Mismatch。

代码

来源：problems/cf1202F/solution.cpp

/* Author: likely
 * Time: 2026-06-08 05:15:00
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    ll a,b,n,ans,l,r,g,a_low,a_high,b_low,b_high,cur;
    cin>>a>>b;
    n=a+b;
    ans=0;
    l=1;
    while(l<=n){
        g=n/l;
        if(a<g or b<g){
            l=n/g+1;
            continue;
        }
        r=n/g;
        a_low=(a+g)/(g+1);
        a_high=a/g;
        b_low=(b+g)/(g+1);
        b_high=b/g;
        if(a_low<=a_high and b_low<=b_high){
            cur=min(r,a_high+b_high)-max(l,a_low+b_low)+1;
            if(cur>0) ans+=cur;
        }
        l=r+1;
    }
    cout<<ans<<"\n";
    return 0;
}