P8925题解

题意简述

原点处有一盏灯，左、右各有一面镜子，分别位于 $-L$、$R$。两镜对照产生无穷多个像。$T$ 次询问，每次求左侧或右侧第 $x$ 个像的坐标。

解题思路

$x$ 高达 $10^{10}$，必须直接算出第 $x$ 个像的位置，不能逐次反射。

记左、右镜到原点的距离为 $L$、$R$。观察左侧前几个像到原点的距离：$2L,\ 2L+2R,\ 4L+2R,\ 4L+4R,\dots$，每往后一个像交替增加 $2R$、$2L$。于是左侧第 $x$ 个像到原点的距离为

$$2\left\lceil\frac x2\right\rceil L+2\left\lfloor\frac x2\right\rfloor R,$$

坐标取其相反数。右侧完全对称，把 $L$、$R$ 的系数互换即可。

整数实现中 $\left\lceil\frac x2\right\rceil$ 为 $(x+1)/2$，$\left\lfloor\frac x2\right\rfloor$ 为 $x/2$。每次询问 $O(1)$ 作答，坐标可达 $10^{17}$ 量级，用 $64$ 位整数。

时间复杂度为 $O(T)$。

参考代码

293 Bcpp

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	ll l,r;
	cin>>t>>l>>r;
	while(t--)
	{
		char c;
		ll x;
		cin>>c>>x;
		ll a=(x+1)/2,b=x/2;
		cout<<(c=='L'?-2*(a*l+b*r):2*(a*r+b*l))<<'\n';
	}
	return 0;
}