ABC341D

标签：ABC341D int mid long INF lcm

ABC 341 D

赛事思路：

• 按 lcm 分周期处理
• 不可行的理由：
  • a， b 在同一个周期里 排列无规律
  • lcm 可能很大（周期内最多能有 2e5 左右个数）， 不好预处理

正解

• 二分（二分结果的值）

  • 答案序列内数的排名单增
  • 排名容易 Check
    • mid / n + mid / m - (mid / lcm) * 2

  # include <iostream>
  # include <algorithm>
  # define int long long
  using namespace std;
  const int INF = (int)1e18;
  
  int n, m, k;
  
  signed main(){
  //	freopen("1.in", "r", stdin);
  	
  	cin >> n >> m >> k;
  	int lcm = n * m / __gcd(n, m);
  	
  	int l = 1, r = INF;
  	while(l < r){
  		int mid = (l + r) / 2;
  		int num = mid / n + mid / m - (mid / lcm) * 2;
  		if(num >= k){
  			r = mid;
  		}else{
  			l = mid + 1;
  		}
  	}
  	cout << l << "\n";
  }
  

标签：ABC341D,int,mid,long,INF,lcm
From： https://www.cnblogs.com/wangyangjena/p/18020824