描述
题解
十分有趣的一个数列问题,只要找到 S 的规律即可,首先我们可以知道,S 所能覆盖的区间一定是 [kA, kB](k = 1, 2, 3, …),所以我们只需要逐个区间考虑与 T 的交集,但是这样并不够快,因为我们还有一个规律没有开发出来,仍然属于暴力解题的范畴。而这个规律只需要多算几个 k 就明了了,随着 k 的增大,S 所能覆盖的区间之间的空隙会一点点变小,最后出现粘连或者交叉,也就是说,从这里开始以后的所有数字均能用 S 的元素和覆盖,所以呢,我们只需要特殊情况考虑全,这个问题也就迎刃而解了。剩下的也就是细心的问题了,我就是粗心,少考虑了一种情况,导致坑了二十多分钟。/(ㄒoㄒ)/~~
代码
#include <iostream>
using namespace std;
typedef long long ll;
int T;
ll A, B, X, Y;
int main(int argc, const char * argv[])
{
cin >> T;
while (T--)
{
cin >> A >> B >> X >> Y;
ll res = 0;
for (int i = 1; i; i++)
{
if (i * A <= X)
{
if (i * B >= (i + 1) * A - 1)
{
res += Y - X + 1;
break;
}
else if (i * B >= Y)
{
res += Y - X + 1;
break;
}
else if (i * B >= X)
{
res += i * B - X + 1;
}
}
else if (i * B <= Y)
{
if (i * B >= (i + 1) * A - 1)
{
res += Y - i * A + 1;
break;
}
else
{
res += i * B - i * A + 1;
}
}
else
{
if (i * A <= Y)
{
res += Y - i * A + 1;
}
break;
}
}
cout << res << '\n';
}
return 0;
}