题目描述
给定 a 和 b。若一个正整数能够被 a 整除或者被 b 整除，则我们称该正整数为神奇数字。现在给定 n，请你求出第 n 个神奇数字。
答案可能很大，输出对答案mod 10^9+7
输入格式
第一行三个整数 n，a，b。
输出格式
输出一行，代表答案。
样例输入
1 2 3
样例输出
2
样例输入
4 2 3
样例输出
6
数据规模
1 \le n \le 10^9,2 \le a,b \le 4 \times 10^4 。
我的写法 TLE\,\,40pts
思路：
先枚举一下 \min{a,b} \sim lcm(a,b) 内的满足条件的数，看做一次循环，则共有 \frac{n}{cnt} （cnt为一次循环内的满足条件数个数），接着再枚举最后的一部分就可以了。可是前面的枚举还是会T掉。
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int a,b,n;
cin>>n>>a>>b;
int cnt=0;
int lcm=a/__gcd(a,b)*b;
for(int i=min(a,b);i<=lcm;i++){
if(i%a==0||i%b==0){
cnt++;
}
if(cnt==n){
cout<<i%1000000007;
return 0;
}
}
int p=n%cnt;
int q=n/cnt*lcm;
cnt=0;
for(int i=q+min(a,b);i<=q+lcm;i++){
if(i%a==0||i%b==0){
cnt++;
}
if(cnt==p){
cout<<i%1000000007;
return 0;
}
}
}
球思路（送解决）
