学步园

http://poj.org/problem?id=2773

求第k大与n互质的数，二分+莫比乌斯水过

据说裸用容斥原理可以0ms

对此我表示hehe

我的时间复杂度：O(n+qsqrt(n)logn)

下面的：O(n+qsqrt(n)+qlogn*(2^(logn)))（如果同样是线性筛）

尼玛这根本不是多项式的复杂度啊。

【update】我x我犯逗了2^logn肿么不是多项式。。。。。。？

//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive    Blog:http://willinglive.cf
************************************************/
#define rep(i,l,r) for(int i=(l),___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=(r),___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const LL read()
{LL r=0,k=1;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';return k*r;}
/////////////////////////////////////////////////
const int N=1000000;
int prim[100000],mu[N+10],cnt;
bool flag[N+10];
int n,k,sq;
int a[2000];
/////////////////////////////////////////////////
void init_prim_mu()
{
	mu[1]=1;
	rep(i,2,N)
	{
		if(!flag[i]) prim[++cnt]=i,mu[i]=-1;
		for(int j=1;j<=cnt && i*prim[j]<=N;j++)
		{
			flag[i*prim[j]]=1;
			if(i%prim[j]==0)
			{
				mu[i*prim[j]]=0;
				break;
			}
			else mu[i*prim[j]]=-mu[i];
		}
	}
}
int cal(int x)
{
	int res=0;
	rep(i,1,*a)
	{
		res+=x/a[i]*mu[a[i]];
	}
	return res;
}
/////////////////////////////////////////////////
void solve()
{
	init_prim_mu();
	while(~scanf("%d%d",&n,&k))
	{
		int l=1,r=1000000000,mid;
		sq=(int)sqrt((double)n);
		*a=0;
		rep(d,1,sq) if(n%d==0)
		{
			a[++*a]=d;
			if(d*d!=n) a[++*a]=n/d;
		}
		while(l<r)
		{
			mid=l+r>>1;
			if(cal(mid)<k) l=mid+1;
			else r=mid;
		}
		printf("%d\n",l);
	}
}
/////////////////////////////////////////////////
int main()
{
    #ifndef _TEST
    freopen("std.in","r",stdin); freopen("std.out","w",stdout);
    #endif
    solve();
    return 0;
}

贴上神奇的裸容斥原理

From:http://blog.163.com/happyliyifan@126/blog/static/37462772201311315033520/

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#define N 1005
using namespace std;
int n , k, K, cnt;
int mark[N + 10], prime[N];
int a[11];

void init()
{
    cnt = 0;
    for(int i = 2; i <= N; i++)
    {
        if(!mark[i])
        {
            prime[cnt++] = i;
            for(int j = 2 * i; j <= N; j += i)
            {
                mark[j] = 1;
            }
        }
    }
}

void getprime()
{
    int tmp = n;
    k = 0;
    for(int i = 0; i < cnt && prime[i] * prime[i] <= n; i++)
    {
        if(tmp % prime[i] == 0)
        {
            a[k++] = prime[i];
            while(tmp % prime[i] == 0)
            {
                tmp /= prime[i];
            }
        }
    }
    if(tmp != 1)
    {
        a[k++] = tmp;
    }
}

int judge(int num)
{
    int sum = 0;
    for(int i = 1; i < (1 << k); i++)
    {
        int tmp = 1;
        int t = 0;
        for(int j = 0; j < k; j++)
        {
            if((1 << j) & i)
            {
                t++;
                tmp = tmp * a[j];
            }
        }
        if(t % 2 == 1)
        {
            sum += num / tmp;
        }
        else
        {
            sum -= num / tmp;
        }
    }
    return num - sum;
}

int main()
{
    init();
    while(scanf("%d%d", &n, &K) != -1)
    {
        getprime();
        int l = 1, r = 1000000000, mid, ans;
        while(l <= r)
        {
            mid = (l + r) >> 1;
            int pt = judge(mid);
            if(pt >= K)
            {
                if(pt == K) ans = mid;
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
            }
        }
        printf("%d\n", ans);
    }
}