首页 > 代码库 > 容斥原理
容斥原理
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 7;
int a[N];
LL ans,all;
void dfs(int x, LL y){
if(x>a[0]){ans+=all/y; return;}
dfs(x+1,y); dfs(x+1,-y*a[x]);
}
LL count(LL x){
ans=0,all=x;
dfs(1,1);
return ans;
}
int main(){
int m,k;
while(!cin.eof()){
cin>>m>>k;
a[0]=0;
for(int i=2;i*i<=m;++i)
if(m%i==0){
a[++a[0]]=i;
for(;m%i==0;m/=i);
}
if(m>1)a[++a[0]]=m;
LL l=1,r=1e18,mid;
for(;l<=r;){
mid=(l+r)>>1;
if(count(mid)>=k)r=mid-1;
else l=mid+1;
}
cout<<l<<endl;
}
return 0;
}
容斥原理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。