求最小正整数$H$,使正整数$1∼H$中存在$n$个数不能被质数$x$整除
设$b=n \% (x-1),a=H \% x,k=(H-a)/x,h=(n-b)/(x-1)$(其中$b,a,k,h$都为整数),即求满足$H-k \ge n$的$H$最小值,$H=k*x+a$,其中$k$优先取最小值。
$H-k \ge n \Leftarrow k \ge h+(b-a)/(x-1)$,其中$0 \le b \le x-2,0 \le a \le x-1$,所以$h-1 \le h+(b-a)/(x-1) < h+1 $
当$b==0$时,$a=x-1$使$k$最小为$h-1$,$H=k*x+a=n/(x-1)*x-1$;
当$b!=0$时,$a=b$使$k$最小为$h$,$H=k*x+a=(n-n \% (x-1))/(x-1)*x+n \% (x-1)$
由题可知H要同时满足以下三个条件的最小值
1.正整数$1∼H$中存在$N$个数不能被质数$x$整除
2.正整数$1∼H$中存在$M$个数不能被质数$y$整除
3.正整数$1∼H$中存在$N+M$个数不能被数$x*y$整除
取分别满足这三种情况的三个H最小值中的最大值即为最终结果
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,x,y;
cin>>n>>m>>x>>y;
int a,b,c;
if(n%(x-1)==0) a=n/(x-1)*x-1;
else a=(n-n%(x-1))/(x-1)*x+n%(x-1);
if(m%(y-1)==0) b=m/(y-1)*y-1;
else b=(m-m%(y-1))/(y-1)*y+m%(y-1);
if((m+n)%(x*y-1)==0) c=(m+n)/(x*y-1)*x*y-1;
else c=((m+n)-(m+n)%(x*y-1))/(x*y-1)*x*y+(m+n)%(x*y-1);
cout<<max(a,max(b,c))<<endl;
}