【ARC127F】±AB

给定 \(a,b,L,R\)，找到最小的 \(p\geq 0\)，使得 \(pa\bmod b\in[L,R]\)。

设 \(qb\leq pa<(q+1)b\)。

等价于找到最小的 \(q\geq 0\)，使得存在 \(qb\leq pa<(q+1)b\) 满足 \(pa\bmod b\in [L,R]\)，即存在 \(p\) 满足 \(pa-qb\in[L,R]\)。

设 \(b=ka+r\)，转化为找到最小的 \(q\geq 0\)，使得存在 \(p\) 满足 \((p-qk)a-qr\in [L,R]\)。

注意到 \(q\) 确定后，\(p\) 的取值能使得 \((p-qk)a-qr\) 取到模 \(a\) 同余于 \(-qr\) 的任何数，于是，我们只需存在 \(x\in [L,R]\) 使得 \(-qr\equiv x\pmod a\) 即可。

若存在 \(x\in [L,R]\) 使得 \(x\) 是 \(a\) 的倍数，则 \(q=0\)；否则，我们需找到最小的 \(q\geq 0\) 使得 \(qr\bmod a\in[-R\bmod a,-L\bmod a]\)。

这就递归到了子问题。

#include<bits/stdc++.h>

#define int long long

using namespace std;

int mod(int x,int b)
{
	return (x%b+b)%b;
}

int calc(int a,int b,int L,int R)//find min p and exist x in [L,R] that pa = x (mod b)
{
	if(R-L+1>=b) return 0;
	L=mod(L,b),R=mod(R,b);
	if(L>R) return 0;
	int k=b/a,r=b-k*a;
	int q=calc(r,a,-R,-L);
	return (q*b+L+a-1)/a;
}

int solve(int a,int b,int V,int M)
{
	int p=calc(a,b,M-a+1-V,b-1-V);
	int q=(V+p*a)/b;
	assert(V+p*a-q*b+a>M);
	return p+q;
}

signed main()
{
	int T; cin>>T;
	while(T--)
	{
		int A,B,V,M;
		cin>>A>>B>>V>>M;
		if(A+B<=M+1)
		{
			printf("%lld\n",M+1);
			continue;
		}
		printf("%lld\n",solve(A,B,V,M)+solve(A,B,M-V,M)+1);
	}
	return 0;
}

原文地址：http://www.cnblogs.com/ez-lcw/p/16837096.html