题解：P10788 [NOI2024] 分数

Larunatrecy · 2024-08-04 12:59:25 · 题解

首先假设 n\geq m，我们考虑如下过程：

• 初始时 (p,q)=(1,0)。
• 枚举 u=2k(k\geq 1)，令 (p,q)\to (q+up,p)。

可以证明，该过程可以不重不漏生成所有 >1 的完美正分数 \frac{p}{q}。

对于 <1 的完美正分数，只需要在 p\leq m 时让贡献多一即可。

考虑该过程中的所有 u 构成的序列：u_1,u_2……，设其中的最大值是 x，如果有多个则取最靠前的一个，那么序列变成 u_1,u_2…… u_{k-2},x,u_k……，我们先不枚举 x 的值是多少，而是把当前的分数表示成 (a+bx,c+dx) 的形式，并且维护 x 的下界，在完成搜索的时候 O(1) 计算满足要求的 x。

具体来说，搜索过程分成两部分，x 之前和之后。

算答案就是 \min(\lfloor \frac{n-a}{b}\rfloor,\lfloor \frac{m-c}{d}\rfloor)-v+1+\min(\lfloor \frac{m-a}{b}\rfloor,\lfloor \frac{m-c}{d}\rfloor)-v+1，前边是 >1 的，后边是 <1 的。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,m;
LL res=0;
int cl(int a,int b){return b==0?1e9:a/b;}
void dfs(int a,int b,int c,int d,int v)
{
    res+=max(0,min(cl(n-a,b),cl(n-c,d))-v+1);
    res+=min(cl(m-a,b),cl(n-c,d))-v+1;
    for(int u=1;;u++)
    {
        if(c+2*a*u+(d+2*b*u)*max(v,u)>m||a+b*max(v,u)>n)break;
        dfs(c+2*a*u,d+2*b*u,a,b,max(u,v));
    }
}
void dfs1(int x,int y,int v)
{
    for(int u=1;;u++)
    {
        if(x+2*max(u+1,v)*(y+2*u*x)>m||y+2*u*x>n)break;
        dfs1(y+2*u*x,x,max(v,u+1));
    }
    dfs(y,2*x,x,0,v);
}
int main()
{
    cin>>n>>m;
    if(n>m)swap(n,m);
    dfs1(1,0,1);
    cout<<res;
    return 0;
}