题解：P10788 [NOI2024] 分数

C1942huangjiaxu · 2024-07-26 22:01:58 · 题解

2024.8.23 upd: 修复了参考代码中 n\lt b 时出错的问题。

本题解主要讲述官方题解怎么实现。

首先可以发现，每个分数都可以由 2 开始，若干 +2，取倒数，这样的若干次操作得到，并且每个分数操作序列唯一。

这里不妨假设 n\le m，我们只考虑 \lt 1 的分数。

那么每次操作，相当于，加上一个偶数 u，然后取倒数。

也就是官方题解中连分数的形式：

假设当前的值为 \cfrac a b，那么加上 u 后取倒数，就是 \cfrac {b}{bu+a}。

我们搜索中，把 u 中的最大值设为 x，统计答案时直接统计所有可能的 x，官方题解中说明，这样的搜索量是可以接受的。

于是，我们的搜索过程就可以描述为，先进行若干次操作，得到分数 \cfrac{a}{b}，然后加入最大值 x，搜索分数 \cfrac {ax+b}{cx+d}，同时我们要维护最大值 x 的下界来统计答案。

将不可能成为答案的状态剪枝，最后大概统计 4\times 10^8 次答案。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long ans;
void dfs1(int a,int b,int c,int d,int v){
    if(1ll*a*v+b>n)return;
    ans+=max(0,min(!a?m:(n-b)/a,(m-d)/c)-v+1)+max(0,(n-d)/c-v+1);
    for(int u=1;;++u){
        int A=2*c*u+a,B=2*d*u+b;
        if(1ll*A*max(v,u+1)+B>m)break;
        dfs1(c,d,A,B,max(v,u+1));
    }
}
void dfs2(int a,int b,int v){
    for(int u=1;;++u){
        int c=2*u*b+a;
        if(2ll*c*max(v,u)+b>m)break;
        dfs2(b,c,max(v,u));
    }
    dfs1(0,b,2*b,a,v);
}
int main(){
    scanf("%d%d",&n,&m);
    if(n>m)swap(n,m);
    dfs2(0,1,1);
    printf("%lld\n",ans);
    return 0;
}