题解归档 - cf2232F

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

• 本地编号：cf2232F
• 本地来源：problems/cf2232F/idea.md
• 题目链接：https://codeforces.com/contest/2232/problem/F
• 原始标题：CF2232F — The Cake Is a Lie

思路

CF2232F — The Cake Is a Lie

题意

有 n 张饼、两个平底锅。初始 min(n,2) 张饼在盘上，熟度均为 0。

• 煮 1 分钟：盘 1 上饼 +a，盘 2 上饼 +b（若盘上无饼则不加）。
• 上菜：立刻端走盘 1 的饼；盘 2 的饼移到盘 1；若还有生饼则新饼放到盘 2。可连续上菜（不耗时）。

熟度恰好为 k 的饼算完美。求最多能端出多少张完美饼。

数学记录

• pattern: affine recurrence + gcd divisibility.
• claim: 设 x_i 为第 i 次上菜前等待的分钟数，则第 1 张完美 iff a*x_1=k，第 i>=2 张完美 iff b*x_{i-1}+a*x_i=k。
• necessary: gcd(a,b) | k 才可能让任意 i>=2 完美；第 1 张还要求 a | k。
• sufficient: 一段连续完美饼等价于这条一阶线性递推存在非负整数解；非完美位置可以把后续递推重新启动。
• brute/check: BFS 枚举小 n,a,b,k 的所有可达熟度状态，与主解对拍。

关键观察

1. 必要条件：k 必须被 gcd(a,b) 整除，否则无解。之后令 a,b,k 都除以 g=gcd(a,b)，下述均指约化后的值。

2. 单盘路径：

   • 只在盘 1 煮：a·t = k → t = k/a（需整除）。
   • 先在盘 2 煮 x 分钟、再移到盘 1 煮：b·x + a·t = k。
3. 链式上菜：一次煮 x 分钟后连续上菜，则「曾在盘 2 上的那张」熟度为 b·x（不再额外在盘 1 煮），下一张在盘 1 上的为 a·x，再下一张又回到 b·x 型……形成递推
   [
   a·x_{m+1} + b·x_m = k
   ]
   从某个合法 x_1 出发可迭代生成一串烹饪时长。
4. 批量并行：若连续 v+1 个方程
   a·x_{m+2}+b·x_{m+1}=k, … 可同时满足（同一组 x），则每 v+1 张饼可稳定产出 1 张完美饼（其余可浪费）。差分满足 a | (x_{m+2}-x_{m+1})、b | (x_{m+3}-x_{m+2}) 等，可归纳出 m 的倍增结构。

算法

1. k % gcd(a,b) != 0 → 输出 0。
2. 约化后若 a=b=1 → 每张饼单独煮 k 分钟即可，答案 n。
3. 前缀链：若 k % a == 0，从 x=k/a 出发反复
   x ← (k - b·x) / a（需非负且整除），每步多 1 张完美饼，直到失败或 n 用尽。

4. 批量因子 v：

   • 若 k % (a+b) == 0，则 v 视为无穷（每 a+b 型批量极优）。
   • 否则设 a>b（交换保证），用扩展欧几里得在递增的 m = b, b·a, b·a², … 上找最大 v，使得前 v 步递推方程可同时成立。
5. 剩余 n 张饼按每 v+1 张贡献 1 张完美：ans + n - ⌈n/(v+1)⌉ 的变形即代码中 ans + (n - (n+v)/(v+1))。

复杂度

每测 O(log k) 次扩欧与倍增，总 O(t log k)。

实现注意

• 题面样例第 6 组已更新为 100 1 2 2 → 67（非旧版的 1 2 1 100）。

验证

• 官方 7 组样例全部通过。
• solution/brute/gen 均编译到 build/cf2232F/。
• BFS brute 对拍：定向 + 随机小范围 2548 组通过。
• BFS brute 对拍：n<=8, a,b<=20, k<=100 随机 5000 组通过。
• 大数冒烟：1000 组 n,a,b,k<=1e9 返回 1000 个答案，无超时/崩溃。

代码

来源：problems/cf2232F/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:10:05
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll xg,yg;
ll egcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1;
        y=0;
        return a;
    }
    ll x1,y1;
    ll d=egcd(b,a%b,x1,y1);
    x=y1;
    y=x1-y1*(a/b);
    return d;
}
int main(){
    ll t,n,a,b,k,g,ans,cur,x1,x2,m,v,i,pd;
    cin>>t;
    while(t--){
        cin>>n>>a>>b>>k;
        g=__gcd(a,b);
        if(k%g){
            cout<<0<<"\n";
            continue;
        }
        a/=g;
        b/=g;
        k/=g;
        if(a==1 and b==1){
            cout<<n<<"\n";
            continue;
        }
        ans=0;
        if(k%a==0){
            ans++;
            n--;
            cur=k/a;
            while(n>0){
                if(k-cur*b<0)
                    break;
                if((k-cur*b)%a)
                    break;
                cur=(k-cur*b)/a;
                ans++;
                n--;
            }
        }
        v=0;
        if(k%(a+b)==0)
            v=1000000000LL;
        else{
            if(a<b)
                swap(a,b);
            m=b;
            while(1){
                egcd(a+b,m,xg,yg);
                if(xg<0){
                    xg+=m;
                    yg-=a+b;
                }
                xg*=k;
                yg*=k;
                pd=xg/m;
                xg-=pd*m;
                yg+=pd*(a+b);
                if(m/b*yg+xg<0)
                    break;
                pd=1;
                x1=xg;
                x2=m/b*yg+xg;
                for(i=0;i<v;i++){
                    if(a*x1+b*x2!=k)
                        pd=0;
                    if((k-b*x1)%a){
                        pd=0;
                        break;
                    }
                    x2=x1;
                    x1=(k-b*x1)/a;
                }
                if(!pd)
                    break;
                v++;
                if(a>k/m)
                    break;
                m*=a;
            }
        }
        cout<<ans+(n-(n+v)/(v+1))<<"\n";
    }
    return 0;
}