Atcoder341 d

前面的三道题的都做出来虽然花的时间比较久，但是第四题就不会了，看了许多题解终于弄懂了。

#### 问题陈述

给你三个正整数 N、M 和 K。这里，N和M是不同的。 请列出能被N和M中的一个整数整除的K个最小正整数。

输入样例

2 3 5

输出样例

9

题解：首先对于这道题，可以用暴力，但是数据量感人所以大部分会t。所以就是说需要有优化的方法。

对于这道题，我们可以将k作为一个基准值，可以用二分法找到想要的数字，所以对于这里我们可用二分进行二分答案的操作，因为是一个整除所以说明两个的公因数是不行的，就比如6，被2和3整除。这个就要被去掉，所以我们需要找到两个数的最大公因数，所以就是找到最小公倍数。然后我们举个例子：如果我们想要知道15以内的合法序列的数，我们可以求20以内2的个数:20/2,对于3的个数就是:20/3，然后我们需要去掉两者的最小倍数，但是在2的时候算了一次，又在3的时候算了一次，所以我们需要减掉两倍的20/两者的最大公因数。所以我们可以抽象成数学，二分的就是mid,所以我们判断x是k，我们可以写成[mid/n]+[mid/m]-2*[mid/lcm(n,m)]然后来判断大小

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

long long gcd(long long x,long long y){
	if(x>y)swap(x,y);
	if(y%x==0)return x;
	return gcd(y%x,x);
}

int main() {
	long long n,m,x,k;
	cin>>n>>m>>k;
	x=(n*m)/gcd(n,m);
	long long l=0,r=(long long)2e+18,mid,y;
	while((l+1)<r){
		mid=(l+r)/2;
		y=(mid/n)+(mid/m)-2*(mid/x);
		if(y<k)l=mid;
		else r=mid;
	}
	cout<<r<<endl;
	return 0;
}