「2019五校联考-雅礼」大凯的疑惑

首先判断是否有无穷解，即判断$\gcd(a,b)>1$时有无穷解

接下来我们由小凯的疑惑知道最大的无法表示的数是$ab-a-b$，这能确定一个上界

考虑计算$1,R$中能用$a,b$表示出来的数

因为$\gcd(a,b)=1,R<ab$，所以每个数最多只有一种构成法，可以枚举其包含了几个$b$，剩下的部分直接任意放$a$

即得到计算能够被构成的个数的方法为$\begin{aligned}\sum_{i=0}^{\lfloor \frac{R} {a}\rfloor} \lfloor \frac{R-ib} {a}\rfloor+1 \end{aligned}$

其中+1是计算了包含0个$a$的情况

如果二分答案，复杂度为$O(a\log (ab))$，恐怕难以通过

优化：

我的思路是是先确定了$\lfloor \frac{R} {a}\rfloor$，那么此时确定了所有$b$的个数的贡献

那么考虑枚举，找到答案所属的$\lfloor \frac{R} {a}\rfloor$的区间，在这段区间里，判断一个数$x$是否可以被构成即:

$x\equiv ib\pmod a(i\leq \lfloor \frac{R} {a}\rfloor)$，即考虑了不同$b$的个数的贡献

用一个数组存下$ib\bmod a$，那么可以$O(1)$判断一个数是否合法，如果直接for过去是$O(b)$的

显然这在一段中，构成情况每$a$个一循环，那么先快速跳循环即可

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

const int N=2e7+10;

ll a,b,k;
ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); }
bool mk[N];
int main() {
	freopen("math.in","r",stdin),freopen("math.out","w",stdout);
	scanf("%lld%lld%lld",&a,&b,&k);
	if(gcd(a,b)!=1 || a==1) return puts("-1"),0;
	if(a>b) swap(a,b);
	if(k==1) return printf("%lld\n",a*b-a-b),0;
	ll s=(a-1)*(b-1)/2,c=0; // s为总的个数
	if(s<k) return puts("-1"),0;
	k=s-k+1; // 改为求第k小
	int p=mk[0]=1;  // p为所属区间
	rep(i,1,a-1) {
		c+=i*b/a;
		ll t=i*(b-1)-c; // t为这段区间内无法被表示的个数
		if(t>=k){ p=i; break; }
		mk[i*b%a]=1;  // 把区间内的ib mod a 放进去
	}
	k-=(p-1)*(b-1)-(c-p*b/a); //还需要做的个数
	ll l=(p-1)*b+1,d=l%a; //l为区间开始位置
	ll i=l+(k-1)/(a-p)*a; // 每个长度为a的循环中已经有p个位置被标记，可以被表示，因此还有a-p个位置无法表示
	k-=(k-1)/(a-p)*(a-p); // 跳过循环
	for(;;++i,d++,d==a&&(d=0)) if(!mk[d] && --k==0) return printf("%lld\n",i),0; // 暴力for最后a个
}