[CF1500B] Two chandeliers

[CF1500B] Two chandeliers - 二分,数论

Description

给你两个序列，一个长度为 n，一个长度为 m，这两个序列的数都是两两互不相同的，这两个序列都是可以无限循环的，这两个序列里面的值都是小于等于 (2*max(n,m)) ，问当这两个序列长度为多少是，最少有 (k le 10^{12}) 个位置的数是不同的。

Solution

假设 (n le m)，先按步长 (frac {nm} {gcd(n,m)}) 走，再按步长 (n) 走，最后按步长 (1) 走

预处理出 (c[i]) 表示 A 从 1 走到 n，B 从 (i) 开始走 n 步的过程中，产生的不同次数是多少

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

#define int long long

const int N = 1e6 + 5;
int n, m, k, a[N], b[N], p[N], c[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int j = 0; j < m; j++)
        cin >> b[j];
    if (n > m)
    {
        swap(a, b);
        swap(n, m);
    }
    memset(p, -1, sizeof p);
    for (int i = 0; i < n; i++)
        p[a[i]] = i;
    for (int i = 0; i < m; i++)
        if (~p[b[i]])
            c[(i - p[b[i]] + m) % m]++;
    for (int i = 0; i < m; i++)
        c[i] = n - c[i];
    int g = __gcd(n, m);
    int ans = 0;
    // 大轮
    int sum = 0;
    int delta = 0;
    for (int i = 0; i < m / g; i++)
        sum += c[delta], (delta += n) %= m;
    ans += (k - 1) / sum * (n * m / g);
    k -= (k - 1) / sum * sum;
    // 小轮
    for (int i = 0; i < m / g; i++)
        if (k > c[delta])
            k -= c[delta], ans += n, (delta += n) %= m;
    // 单格
    for (int i = 0; i < n && k; i++)
    {
        if (a[i] != b[(i + delta) % m])
            --k;
        ++ans;
    }
    cout << ans << endl;
}