POJ2773 Happy 2006

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

Description

Two positive integers are said to be relatively prime to each other if the Great Common Divisor (GCD) is 1. For instance, 1, 3, 5, 7, 9...are all relatively prime to 2006.

Now your job is easy: for the given integer m, find the K-th element which is relatively prime to m when these elements are sorted in ascending order.

Input

The input contains multiple test cases. For each test case, it contains two integers m (1 <= m <= 1000000), K (1 <= K <= 100000000).

Output

Output the K-th element in a single line.

题意：找出第k小的与m互素的数。

方法1：由gcd(a,b)=gcd(b,a%b)可得gcd(a+k*b,b)=gcd(a,b)

如果a与b互素，则b×t+a与b也一定互素，如果a与b不互素，则b×t+a与b也一定不互素

那么1~b满足的个数，和b+1~2b，2b+1~3b...是相同的，

用欧拉函数求出1~b与b互素的数的个数，就很好做了，最后一组暴力搞一下就行了。

#include<cstdio>
#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long

ll m,k;

ll euler_phi(ll n)
{
	ll m=sqrt(n+0.5);
	ll ans=n;
	for(int i=2;i<=m;i++)if(n%i==0)
	{
		ans=ans/i*(i-1);
		while(n%i==0)n/=i;
	}
	if(n>1)ans=ans/n*(n-1);
	return ans;
}

int main()
{
//	freopen("input.in","r",stdin);
	while(cin>>m>>k)
	{
		int cnt=0;
		ll phi=euler_phi(m);
		ll num=k%phi,base=k/phi*m;
		if(!num)num=phi,base-=m;
		for(int i=1;i<=m;i++)
		{
			if(__gcd((ll)i,m)==1)cnt++;
			if(cnt==num)
			{
				cout<<base+i<<endl;
				break;
			}
		}
	}	
	return 0;
}

方法2：1~n中与m互素的数的个数随n单调递增，那么二分n，直到前n个数与n互素的数为k-1，最后一个暴力找就行了。

check()函数和hdu4135https://blog.csdn.net/Wen_Yongqi/article/details/86776386 是一样的，枚举素因子，用容斥定理做。

这题出了些故障，和标程在最大数据范围对拍找不出错，最后原来是。。。

我一组要找出前n个数含有k-1个与m互素的数，那k==1的话，没有0个的呀，每轮初始化一下ans=1就好了。

#include<cstdio>
#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long

ll m,k,ans;

ll solve(ll num,ll n)
{
	vector<int> prime;vector<ll> que;
	ll m=sqrt(n+0.5);
	for(int i=2;i<=m;i++)if(n%i==0)
	{
		prime.push_back(i);
		while(n%i==0)n/=i;
	}
	if(n>1)prime.push_back(n);
	que.push_back(-1);
	for(int i=0;i<prime.size();i++)
	{
		int k=que.size();
		for(int j=0;j<k;j++)que.push_back(prime[i]*que[j]*-1);
	}
	ll ans=0;
	for(int i=1;i<que.size();i++)ans+=num/que[i];
	return num-ans;
}

int main()
{
//	freopen("input.in","r",stdin);
	while(cin>>m>>k)
	{	
		ans=1;
		ll l=1,r=(1LL<<60),mid;
		while(l<=r)
		{
			mid=(l+r)/2;
			ll ret=solve(mid,m);
			if(ret==k-1){ans=mid+1;break;}
			if(ret>k-1)r=mid-1;
			else l=mid+1;
		}
		while(__gcd(ans,m)!=1)ans++;
		cout<<ans<<endl;
	}	
	return 0;
}

二分函数和下面这样写好像更好一点

                while(l<=r)
		{
			mid=(l+r)/2;
			ll ret=solve(mid,m);
			if(ret>=k){if(ret==k)ans=mid;r=mid-1;}
			else l=mid+1;
		}
		cout<<ans<<endl;