题目描述
给定 a 和 b 。若一个正整数能够被 a 整除或者被 b 整除，则我们称该正整数为神奇数字。现在给定 n ，请你求出第 n 个神奇数字。
答案可能很大，输出对答案 mod 10^9+7
输入格式
第一行三个整数 n，a，b 。
输出格式
输出一行，代表答案。
思路
既然让我们求第 n 个神奇数字，我们二分寻找神奇数字，然后计算当前数字前神奇数字的个数，以此来移动左右指针。
那问题就变成了如何求解一个数字前的所有神奇数字个数。设这个数字为 x ，可能会想到 x/a+x/b 。但是有个问题，可能会有重复情况，例如 n=28,a=4,b=6 ，
a=4 : 4 8 12 16 20 24 28
a=6 : 6 12 18 24
容易发现，重复的部分就是a和b的最小公倍数的倍数 lcm(a,b) 。所以 x 前的神奇数字个数就=n/a+n/b-n/lcm(a,b) 。
又 lcm(a,b)=a*b/gcd(a,b) ，能用递归求得 gcd ，进而求得 lcm(a,b) 。
接下来考虑二分。神奇数字不可能超过 n*min(a,b) ，因为最坏情况下，第 n 个神奇数字就是 a,b 中较小的那个数的 n 倍。所以初始 l=0 ， r=n*min(a,b) 。
设 get(n,a,b)=n/a+n/b-n/lcm(a,b) 。若 get(n,a,b)<n ， l=mid+1 ，否则 r=mid-1 。这里需要注意的是不能直接判断 get(n,a,b)==n ，因为 x 前神奇数字为 n 个的数可能有多个，直到 l=r 时才能确定第 n 个神奇数字。
注意事项
- 不开 long long 见祖宗！我就是之前被坑了， WA 0 QwQ
- 要对 1000000007 取模。但是计算神奇数字个数时不能取模，会导致答案计算错误。
AC代码
#include <bits/stdc++.h>//万能头yyds
#define int long long //开long long，这里我一开始全写的int，懒得改了
using namespace std;
const int mod=1e9+7; //取模
int gcd(int a,int b){ //最大公因数
return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b){ //最小公倍数
return a*b/gcd(a,b);
}
int get(int mid,int a,int b){ //mid前的神奇数字个数
return mid/a+mid/b-mid/lcm(a,b);
}
signed main(){ //因为define int long long 了，所以要用signed定义main函数，否则会报错
int n,a,b;
cin>>n>>a>>b;
int l=1,r=n*min(a,b); //二分开始
while(l<=r){
int mid=(l+r)/2;
if(get(mid,a,b)<n){
l=mid+1;
}else{
r=mid-1;
}
}
cout<<l%mod<<endl;
return 0; //好习惯
}
希望对大家有所帮助～