AT_abc341_d

zibenlun · 2024-02-18 15:46:28 · 题解

思路

题目给出的数据范围很大，所以只能考虑二分，这里我们直接二分答案。对于我们二分出的值，可以通过 mid/n 和 mid/m 求出在它以内分别有多少个 n 和 m 的倍数，之后我们减去重复的，剩下的就是这个数的位次。

重复的部分实际上就是 n 和 m 的最小公倍数。

CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    int x=n*m/(__gcd(n,m));
    int l=0,r=1e18;
    int ans=1e18;
    while(l<=r){
        int mid=(l+r)/2;
        int sum=mid/n+mid/m-mid/x-mid/x;
        if(sum>=k){
            r=mid-1;
            ans=min(ans,mid);
        }
        else {
            l=mid+1;
        }
    }
    cout<<ans;
    return 0;
}