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

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

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

考虑计算 \([1,R](R<ab)\) 中能用 \(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个
}