前言

被大佬WeLikeStudying 花了几乎一下午的时间讲明白之后有感而发决定写一篇题解来报答dalao的恩情。

原题链接 :

U238921 大凯的疑惑（买得到的数目）

所以参考资料就是dalao的题解

题意

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

题解

很相似的一道题是小凯的疑惑（买不到的数目）

不过这题显然是那题的超级加强版（

暴力做法

首先考虑暴力，然后尝试优化。

可惜暴力也需要前置（

由裴蜀定理的推论可知最大的不能被表示的数为(官方题解也给出了这个定理，并且它有自己的名字叫“麦乐鸡定理”)（所以知道这个定理的话就可以爆切小凯了）

并且由同一个推论稍微走远一点就可以得出一个对称性： $x$ 和 $ab-a-b-x$ 有且只有一个可以被表示出来， $ab-a-b-x+1$ 及以后的数都可以被表示，负数都不能被表示，我在数论算法、定理和常用变换的裴蜀定理板块给出了详细证明。

于是对于 $c > \frac{ab-a-b+1}{2} $ 的情况下我们可以 $O(1)$ 计算出答案。具体过程应当不必给出了。

剩下的情况只有 $c \le ab-a-b < ab$ ，所以显然有解时只有一组解。

考虑二分答案，然后枚举一个 $x$ 或 $y$ 进行验证。

我们可以轻松地得到这个式子：

$\sum_{i = 0}^{\lfloor \frac{c}{a}\rfloor} \left \lfloor \frac{c-ai}{b} + 1 \right \rfloor$

现在我们得到了显然不可行的 $O(min(a,b)\log k)$ 的做法力。

45pts做法

这才是一个常规题目的考察内容（

这个做法的内容更类似于小凯的疑惑那道题的证明。

我们可以去掉二分，把每个 $a$ 单独考虑，分别对其加上若干个 $b$ ，也就是 $a$ 个等差数列同时放到数轴上。

于是经过较为复杂的实现，我们得到了以下这份代码：

#include<bits/stdc++.h>
#include<algorithm>
#include<cstdio>
namespace Pozhu{
using namespace std;
#define N 50000005
typedef long long ll;
ll a,b,now,pos;
bool have[N];
// 以a的倍数对数轴进行分块，每块的大小为a
// have数组中存储的是每个块中的第i个位置是否可以产生贡献
// 显然当有一个块中的第i位可以产生贡献时，其后所有块的相应位置都可以产生贡献
// 这里的相对位置的值在数值上等于(ax+by)%a的值
ll k,sum;

void main()
{
    memset(have,0,sizeof(have));
    scanf("%lld%lld%lld",&a,&b,&k);
    if(k > (a-1) * (b-1) >> 1)// 由麦乐鸡定理易得的特判
    {
        printf("%lld\n",((a-1) * (b-1) >> 1) + k-1);
        return;
    }
    for(int i = 0;i <= a;i++)
    {// 枚举每一个以a的倍数为分界线的块中有几个含b的数值做出了贡献（认为0*b不是b做出贡献的情况）
     // 显然a加上小于a个b后的数值在块中的相对位置互不相同（由互质可得）
        if(!i) {have[0] = 1;continue;}//对0特判
        ll count = (i * b / a - (i-1) * b / a) * i;
        // i*b是第一个b做出i次贡献的点即总贡献为i+1的点，除以a得到当前对应的贡献为i+1的第一个块编号
        // 然后减去总贡献为i的第一个块的编号，可以得到总贡献为i的块的数量
        // 最后乘上i得到对应的贡献，所以count是贡献为i的块所能做出的总贡献
        if(k <= count || i == a)
        {// 当剩余贡献可以满足当前需要或剩余贡献为正无穷（i==a，块被填满）时
         // 注意i==a时不能计算出count == inf这样的实际数据，因为b能做出i次贡献的点不存在
            ll block_nth = (i-1) * b / a + (k-1) / i;
            // 计算需要几个贡献为i的块，加上第一个贡献为i的块就是当前块的编号
            k = (k-1) % i;
            // 剩余的k是不足一个块的k-1
            for(int j = 0;j < a;j++)
            {
                //遍历块内的位置，当有一个位置能造成贡献时进行相应统计
                if(!have[j]) continue;
                k--;
                if(k == -1)
                {
                    //此时的j值是我们块内的答案
                    printf("%lld\n",block_nth * a + j);
                    return;
                }
            }
        }
        else k -= count;
        have[b * i % a] = 1;
    }
}

}

signed main()
{
    int T;
    for(scanf("%d",&T);T;T--)
    Pozhu :: main();
    return 0;
}

100 pts做法

毒瘤一点，但用这个就可以去常规题目爆标（

考虑真的二分答案，然后用类欧优化一下check的过程

然后发现几乎成了一道原题P5171
（所以顺便切掉一黑）

我推式子的过程大概是这样的：

$\begin{split} \sum_{i = 0}^{\lfloor \frac{c}{a} \rfloor} \left \lfloor \frac{c-ai}{b} + 1 \right \rfloor &= \sum_{i = 0}^{\lfloor \frac{c}{a} \rfloor} \left \lfloor \frac{(b-a)i +\\c}{b} - i + 1 \right \rfloor \\ &= \left (\sum_{i = 0}^{\lfloor \frac{c}{a} \rfloor} \left \lfloor \frac{(b-a)i +\\c}{b} \right \rfloor \right )- \frac{ \lfloor \frac{c}{a} \rfloor (\lfloor \frac{c}{a} \rfloor + 1) }{2} + \lfloor \frac{c}{a} \rfloor + 1 \\ \end{split}$

虽然std使用了直接带着作为负数的 $-a$ 进行的一个推式子做到了极限数据依然不炸long long ，啊但是我不会推那个所以这种方法写__int128_t也能过。

然后右边可以使用小学奥数 $O(1)$ 求得，左边用类欧求解。
最终我们就得到了复杂度为 $O(\log^2 k)$ 的正解，可以通过本题。

接下来的实现倒是简单的多……或许这才是真正数学题的样子

放下代码罢：

#include<bits/stdc++.h>
#include<algorithm>
#include<cstdio>
namespace Pozhu{
using namespace std;
typedef __int128_t ill;
ill a,b,k;

bool check(ill );
ill like_gcd(ill ,ill ,ill ,ill );

void main()
{
    cin >> a >> b >> k;
    if(k > ((a-1) * (b-1) / 2))
    {
        cout << (a-1) * (b-1) / 2 + k - 1 << '\n';
        return;
    }
	if(a > b) swap(a,b);
	ill l = -1,r = a * b;
	while(l < r)
	{
		ill mid = (l + r + 1) / 2;
		if(check(mid)) l = mid;
		else r = mid - 1;
	}
    cout << l + 1 << '\n';
}

bool check(ill x)
{
	return - (x / a) * (x / a + 1) / 2 + (x / a) + 1 + like_gcd(b-a,x,b,x/a) <= k - 1;
}

ill like_gcd(ill a,ill b,ill c,ill 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);
    }
    ill m = (a * n + b) / c - 1;
	if(m == -1) return 0;
    return n * (m + 1) - like_gcd(c,c-b-1,a,m);
}

}

signed main()
{
    int T;
    for(scanf("%d",&T);T;T--)
    Pozhu :: main();
    return 0;
}