[atARC127F]±AB
阅读原文时间:2023年07月09日阅读:2

(为了方便,以下除$V$外都改为小写字母)

结论1:若$a+b\le m+1$,则答案为$m+1$(即任意$x$都可以被得到)

任取$y\in [0,m]$,由$\gcd(a,b)=1$存在$y-V=pa+qb$,且不妨假设$p\in [0,b)$

不断对$x+a$直至加了$p$次或无法再加,对两种情况分别处理:

1.若为前者,此时再通过若干次$\pm b$一定可以得到$y$

2.若为后者,由$a+b\le m-1$一定可以将$x-b$,进而重复此过程即可

注意到$-b$后一定可以$+a$($a<b$),因此该过程有限,即可以得到$y$

特判此情况后,即有$a+b\ge m+2$

考虑某次$+a$操作后,其不能$-a$(显然无意义)或$+b$(根据$a+b\ge m+2$),那么只能$+a$或$-b$,而同样根据$a+b\ge m+2$,这两个操作中至多只有一个可以执行

类似地分析其余操作,实际上只有两种方案:

1.每一次使用$+a$和$-b$中可以执行的一种操作

2.每一次使用$-a$和$+b$中可以执行的一种操作

注意到是操作是确定的,因此可以看作两条从$V$开始的链

结论2:这两条链上除了$V$以外无公共点

先来证明一条链内部无公共点,不妨以第一条链为例:

注意到每一个点之后的状态是确定的,因此重复即出现循环,同时最小的循环节中不会出现重复的数

任取循环中的某个点$x$,假设其到下一次$x$一共执行了$p$次$+a$和$q$次$-b$,即有$pa=qb$

而$\gcd(a,b)=1$,因此有$a\mid q$且$b\mid p$,同时$p,q\in Z^{+}$,不难得到$p+q\ge a+b\ge m+2$,根据抽屉原理必然存在重复的数,矛盾

再来证明两条链中无公共点(除$V$以外),注意到前者总可以沿着后者的逆过程回到$V$,同时根据唯一性这必然就是该链本身,即重复经过$V$(注意一条链内也不允许重复经过$V$),与之前所述矛盾

综上,即得证

由此,答案即两链链长(指边数)和+1,根据对称性不妨仅考虑第一条链:

不妨考虑该链中$+a$的次数(假设有$p$次,不难推出链长为$p+\lfloor\frac{V+pa}{b}\rfloor$),此时$-b$即可以直接对$b$取模,因此即求最小的$p$使得$(V+pa)mod\ b+a>m$

令$V_{0}=V\ mod\ b$,特判$V_{0}+a>m$的情况,此时显然$p=0$

若$V_{0}+a\le m$,必然要有$V_{0}+pa\ mod\ b<b$,进而原式即为$V_{0}+pa\ mod\ b+a<m$

换言之,原式等价于$pa\ mod\ b\in [L,R]$(其中$L=m-a-V_{0}+1$且$r=b-V_{0}-1$)

不妨假设$b=ka+r$(其中$0\le r<a$)且$qb\le pa<(q+1)b$,那么限制即
$$
pa-qb=(p-qk)a-qr\in [L,R]\Longrightarrow qr\ mod\ a\in [L',R']
$$
(其中$L'$和$R'$即$(-R)mod\ a$和$(-L)mod\ a$,且若其包含0直接取$q=0$即可)

得到满足此条件最小的$q$后(递归),不难解得$p=\lceil\frac{qb+L}{a}\rceil$,且显然其也为最小

过程即为辗转相除,时间复杂度为$o(t\log m)$,可以通过

1 #include
2 using namespace std;
3 #define ll long long
4 int t,a,b,V,m;
5 int get(int a,int b,int L,int R){
6 if (!a)return 0;
7 int q=0;
8 if ((L-1)/a==R/a)q=get(b%a,a,(a-R%a)%a,(a-L%a)%a);
9 return ((ll)q*b+L+a-1)/a;
10 }
11 int calc(int a,int b,int V,int m){
12 int V0=V%b,p=0;
13 if (V0+a<=m)p=get(a,b,m-a-V0+1,b-V0-1);
14 return p+(V+(ll)p*a)/b;
15 }
16 int main(){
17 scanf("%d",&t);
18 while (t--){
19 scanf("%d%d%d%d",&a,&b,&V,&m);
20 if (a+b<=m+1)printf("%d\n",m+1);
21 else printf("%d\n",calc(a,b,V,m)+calc(b,a,V,m)+1);
22 }
23 return 0;
24 }