Warning: session_start(): open(/tmp/sess_167b91b9206b03d670bfd7db72da51f0, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== Atcoder Rugular Contest 123 ======
[[https://atcoder.jp/contests/arc123|比赛链接]]
===== 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;
}
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;
}