nyoj 762:第k个互质数

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=762

直接给代码好了，容斥原理具体看《组合数学》

#include<bits/stdc++.h>using namespace std;typedef long long LL;vector<int> a;    //存储n所有质因子                //不爆int情况下，大概最多10个左右];void getfac(int x){    ;i*i<=x;i++)        )        {            a.push_back(i);            )                x/=i;        }    ) a.push_back(x);}int cal(int x)    //由容斥原理计算1~x中有多少与n互质的自然数{    ,ret=x;    b[++g]=;    //由以下的二重for循环可以做到枚举组合，共2^(a.size())个组合    ;i<a.size();i++)    {        int t=g;        ;j<=g;j++)            b[++t]=-b[j]*a[i],ret+=x/b[t];        g=t;    }    return ret;}int work(int n,int k)    //二分查找{    ,r=2e9;        //cal(l)<k,cal(r)>=k    )        //当r-l=1时，结束循环，此时cal(r)=k    {        ;        if(cal(mid)<k) l=mid;        else r=mid;    }    return r;}int main(){    int n,k;    while(cin>>n>>k)    {        a.clear();        getfac(n);        printf("%d\n",work(n,k));    }}