前言

这是今天粉兔杯每日一题，也是根分日报例题，补一下。

暴力美学——浅谈根号分治 - paulzrm 的博客 - 洛谷博客

题目翻译

给出两个等差数列，求在 $[L,R]$ 之间的交集大小。

等差数列形式为 $ak+b$。

$1\leq a_1,a_2\leq 2\times 10^9,-2\times 10^9 \leq b_1,b_2,L,R \leq 2\times 10^9,L \le R$。

题目思路

观察到 $a$ 大，等差数列在 $[L,R]$ 之间的项数就很少。反之亦然。

所以考虑根号分治。显然阈值 $B=\sqrt{2\times 10^9}\approx44722$。

为了方便，另 $a_1\geq a_2$。

$a_1\leq B$

循环节长度为 $\operatorname{lcm}(a_1,a_2)$ 很显然，那么我们找到第一个重复出现的数即可。

又因为循环节长度为 $\operatorname{lcm}(a_1,a_2)$，所以我们枚举前 $\dfrac{\operatorname{lcm}}{a_1}$ 个在 $a_1k+b_1$ 中的数即可找到第一个重复的数。我一开始实现的时候保守了枚举了 $a_2$ 个，但是我们令 $a_1\geq a_2$，所以其实范围是差不多的。

知道重复的数 $x$ 之后，答案就是 $\lceil\dfrac{R-x+1}{\operatorname{lcm}}\rceil$。

$a_1\gt B$

这是很简单的，因为公差大，所以项数不多，直接枚举 $a_1k+b_1$，判断是否在 $a_2k+b_2$ 中即可。

实现的时候注意一下开始的位置应该是 $\max\{b_1,b_2,L\}$。然后自己微调一下变成等差数列中的某个数就行。

开始循环的位置是 ll start = (max({b1, b2, L}) - b1 + a1 - 1) / a1 * a1 + b1;。

完整代码

$15\ \tt{ms}$ 是目前 CF 最优解了。正解是 exgcd。

CF submission 247832379

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B = 44722;
ll a1, b1, a2, b2;
ll L, R;
int main()
{
    cin >> a1 >> b1 >> a2 >> b2 >> L >> R;
    if (a1 <= a2)
        swap(a1, a2), swap(b1, b2);
    ll start = (max({b1, b2, L}) - b1 + a1 - 1) / a1 * a1 + b1;
    if (a1 <= B)
    {
        ll Lcm = a1 / __gcd(a1, a2) * a2;
        for (ll i = start, j = 1; i <= R && j <= Lcm / a1 + 5; i += a1, j++)
        {
            if ((i - b2) % a2)
                continue;
            return cout << ((R - i + 1) + (Lcm - 1)) / Lcm << endl, 0;
        }
        cout << 0 << endl;
    }
    else
    {
        int ans = 0;
        for (ll i = start; i <= R; i += a1)
            ans += !((i - b2) % a2);
        cout << ans << endl;
    }
    return 0;
}

CF710D Two Arithmetic Progressions 题解