Atcoder Rugular Contest 123

比赛链接

E - Training

题意

给定 $F(x)=\lfloor a_1+\cfrac x{b_1}\rfloor,G(x)=\lfloor a_2+\cfrac x{b_2}\rfloor$，问 $1\sim n$ 中有多少整数 $x$ 满足 $F(x)=G(x)$。

题解

设 $f(x)=a_1+\cfrac x{b_1},g(x)=a_2+\cfrac x{b_2}$，则有四种情况：

$f(x)\in (-\inf,g(x)-1)$，此时 $F(x)\neq G(x)$
$f(x)\in [g(x)-1,g(x))$，此时 $F(x)=G(x)$ 或 $F(x)=G(x)-1$
$f(x)\in [g(x),g(x)+1)$，此时 $F(x)=G(x)$ 或 $F(x)=G(x)+1$
$f(x)\in [g(x)+1,\inf)$，此时 $F(x)\neq G(x)$

显然只有第 $2,3$ 中情况对答案产生贡献。不妨只考虑第 $2$ 种情况，第 $3$ 种情况类似。

首先计算出 $x$ 情况 $2$ 的区间 $[L,R]$，此时有

$$ \sum_{i=L}^R[F(i)==G(i)]=\sum_{i=L}^R(F(i)-G(i)+1)=R-L+1+\sum_{i=L}^R F(i)-\sum_{i=L}^R G(i) $$

其中 $\sum_{i=L}^R F(i),\sum_{i=L}^R G(i)$ 都可以 $O(1)$ 计算，所以总时间复杂 $O(1)$。

查看代码

LL a1,b1,a2,b2;
LL cal(LL k,LL n){
	LL t=n%k;
	LL r=n/k*k*(k-1)/2+t*(t+1)/2;
	return (n*(n+1)/2-r)/k;
}
LL cal(LL a,LL b,LL L,LL R){
	return a*(R-L+1)+cal(b,R)-cal(b,L-1);
}
LL solve(LL L,LL R){
	if(L>R)
	return 0;
	else
	return (R-L+1)-abs(cal(a1,b1,L,R)-cal(a2,b2,L,R));
}
LL upper(LL p,LL q){
	LL ans=p/q;
	while(ans*q<p)ans++;
	return ans;
}
LL lower(LL p,LL q){
	LL ans=p/q;
	while(ans*q>=p)ans--;
	return ans;
}
int main()
{
	int T=read_int();
	while(T--){
		LL n=read_int();
		a1=read_int(),b1=read_int(),a2=read_int(),b2=read_int();
		if(b1==b2){
			if(a1==a2)
			enter(n);
			else
			enter(0);
		}
		else{
			if(b1>b2){
				swap(a1,a2);
				swap(b1,b2);
			}
			LL ans1=solve(max(1LL,upper((a2-a1-1)*b1*b2,b2-b1)),min(n,lower((a2-a1)*b1*b2,b2-b1)));
			LL ans2=solve(max(1LL,upper((a2-a1)*b1*b2,b2-b1)),min(n,lower((a2-a1+1)*b1*b2,b2-b1)));
			enter(ans1+ans2);
		}
	}
	return 0;
}

CVBB ACM Team

目录

Atcoder Rugular Contest 123

E - Training

题意

题解

CVBB ACM Team

用户工具

站点工具

目录

Atcoder Rugular Contest 123

E - Training

题意

题解

页面工具