[ABC341D] Only one of two 的题解

mgcjade · 2024-02-18 09:16:32 · 题解

[ABC341D] Only one of two 的题解

题目大意

求第 k 小的 n 或 m 的倍数（但不能同时是 n 和 m 的倍数）。

思路

一道数学题。

看到这么大的数据范围，肯定不能直接搜索，所以，我们要想办法减少枚举量。

注意到，在 1 到 \gcd(n,m) 这一段区间内，最多有 n+m-2 个数是 n 或 m 的倍数，所以，我们可以寻找答案的大概位置。

不妨假设 n<m，我们需要求的数可以转化为 1 到 \gcd(n,m) 这段区间内第 k \mod (n \div \gcd(n,m) + m \div \gcd(n,m) - 2) 小的数加 k \div (n \div \gcd(n,m) + m \div \gcd(n,m) - 2) \times n \times m \div \gcd(n,m)。

Code

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

const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

ll n, m, k;
ll a, b, c, d, e;
ll ans;
ll i, j;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m >> k;
    if (n > m)
        swap(n, m);
    e = n * m / __gcd(n, m);
    a = e / n, b = e / m;
    c = k / (a + b - 2), d = k % (a + b - 2);
    ans = c * e - n;
    i = n, j = m;
    while (d--)
    {
        if (i < j)
            ans = c * e + i, i += n;
        else
            ans = c * e + j, j += m;
    }
    cout << ans;
    return 0;
}