【LGJOI】大凯的疑惑（买得到的数目）

WeLikeStudying · 2022-08-15 15:38:04 · 题解

• 感谢奆佬，奆佬，奆佬，奆佬的帮助，祝愿其信息学之路光芒璀璨。

题意

原题出处

• 给定 a,b，求能被 ax+by （x,y 是非负整数）表示出来的第 k 小数的大小，a,b,k\le 10^9。
• 多测，测试组数 T\le 10^4。

分析

• 提取公因子，问题变成 a,b 互质的情况。
• 由这题可推导得出你也可以打表找规律，所有大于 ab-a-b 的数都可以被表示出来，且不可以被表示出来的数恰好有 (a-1)(b-1)/2 个：容易用拓欧的知识证明 x 和 ab-a-b-x 有且只有一个不可以被表示出来（它有个学名叫“麦乐鸡定理”），所以如果 k>(a-1)(b-1)/2 可以直接 O(1) 出解。
• 接下来是小于的情况，此时 ax+by=c 满足 c<ab。
• 由拓展欧几里得可知，c<ab 时一个 c 至多对应一个数对 (x,y)，因此二分答案变成计数问题，考虑枚举 x 或 y 问题变为。 \sum_{i=0}^{\lfloor c/a\rfloor}\lfloor(c-ai)/b+1\rfloor
• 我们已经得到了 \min(a,b)\log k 的做法了。

常规出法

• 如果出题出得常规一点，可以去掉二分，得到 \min(a,b) 的做法：
• 考虑原来的问题可以理解成 a 个公差相同的等差数列穿插在一起，所以每个公差能被表示出来的数的数目一定非严格递增，这样枚举复杂度就是 \min(a,b)，代码。

毒瘤出法

• 如果出题出得毒瘤一点，那个式子可以用类欧求解，单次复杂度 O(\log^2a)。
• 个人感觉感觉毒瘤出法不是很优美，而且运算中间结果存在严重的溢出风险，代码。

原题的 AC 代码

#include<bits/stdc++.h>
using ll=long long;
using lll=__int128;
using namespace std;
ll a,b,k;
lll like_gcd(lll a,lll b,lll c,lll n)
{
    if(a==0)return b/c*(n+1);
    if(a>=c||b>=c)return n*(n+1)/2*(a/c)+(n+1)*(b/c)+like_gcd(a%c,b%c,c,n);
    lll m=(a*n+b)/c;
    if(m==0)return 0;
    return n*m-like_gcd(c,c-b-1,a,m-1);
}
ll check(lll c)
{
    return like_gcd(a,c%a,b,c/a)+c/a+1;
}
void solve()
{
    scanf("%lld%lld%lld",&a,&b,&k);++k;ll E=__gcd(a,b);a/=E,b/=E;
    if(k>(a-1)*(b-1)/2)printf("%lld\n",(k+(a-1)*(b-1)/2-1)*E);
    else
    {
        ll l=0,r=a*b;
        while(l<=r)
        {
            ll mid=(l+r)/2;
            if(check(mid)>=k)r=mid-1;
            else l=mid+1;
        }
        printf("%lld\n",(r+1)*E);
    }
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)solve();
    return 0;
}