Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 二分切记，上界要足够大才行。附代码

Posted by Ly86 at 2010-09-20 16:40:48 on Problem 2773
```#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <time.h>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <bitset>
#include <vector>
#include <deque>
#include <utility>
#include <list>
#include <sstream>
#include <iostream>
#include <functional>
#include <numeric>
#include <algorithm>
using namespace std;
template<class T>inline T iabs(const T& v) {return v<0 ? -v : v;}
template<class T>inline T strTo(string s){istringstream is(s);T v;is>>v;return v;}
template<class T>inline string toStr(const T& v){ostringstream os;os<<v;return os.str();}
template<class T>inline int cMin(T& a, const T& b){return b<a?a=b,1:0;}
template<class T>inline int cMax(T& a, const T& b){return a<b?a=b,1:0;}
template<class T>inline int cBit(T n){return n?cBit(n&(n-1))+1:0;}
#define ep 1E-10
#define CLR(arr,v)   memset(arr, v, sizeof(arr))
#define SQ(a)  ((a)*(a))
#define DEBUG(a)     printf("%s = %s\n", #a, toStr(a).c_str())
#define FOR(i,s,e) for( int (i)=(s); (i) < (e) ; i++)
typedef unsigned __int64 u64;
bool is[130000];//用来求素数[1,130000]
int prm[30000];//用来保存素数
int totleprm;//记录素数总个数
u64 gcd(u64 a, u64 b)
{
int c;
if (a<b)
{
c=a;
a=b;
b=c;
}
while (a%b)
{
c=a%b;
a=b;
b=c;
}
return b;
}
u64 getLCM(u64 a, u64 b)
{
return a * b / gcd(a,b);
}

int getprm(__int64 n)
{
int i, j, k = 0;
int s, e = (int)(sqrt(0.0 + n) + 1);
memset(is, 1, sizeof(is));
prm[k++] = 2;
is[0] = is[1] = 0;
for (i = 4; i < n; i +=2) is[i] = 0;
for (i = 3; i < e; i +=2) if(is[i])
{
prm[k++] = i;
for (s = i * 2, j = i * i ; j < n; j +=s)
is[j] = 0;
}
for (; i < n; i +=2)
if (is[i])     prm[k++] = i;
return k;
}
int isOne(u64 n, int i)
{
if ((n & (1 << i) ) == 0)
return 0;
return 1;
}

//求第k个与n互素的数,需要素数表
u64 kThPrim(u64 n, u64 k)
{
if (k == 1)
return 1;
if (n == 1)
return k;
u64 nn = n;
u64 factor[100];
int num = 0;
for (int i=0; i<totleprm && prm[i]*prm[i] <= n; i++)
if (nn % prm[i] == 0)
{
factor[num++] = prm[i];
while (nn % prm[i] == 0 && nn != 1)
nn/=prm[i];
}
if (nn != 1)
factor[num++] = nn;

u64 l = 1;
u64 h = 1000000000;
u64 m;
while ( l < h)
{
m = ( l + h) >> 1;
u64 ans = m ;
FOR(i,1,(1<<num))
{

u64 lcm = 1;
u64 ans_help = 0;
int sum = 0;
FOR(j,0,num)
if (isOne(i,j) == 1)
{
sum++;
lcm = lcm * factor[j];
}
if (sum & 1 )
ans -= m / lcm;
else
ans += m / lcm;
}

if (ans  ==  k)
{
while (gcd(m,n) != 1) m--;
return m;
}
if (ans < k)
l = m + 1;
else
h = m;
}
return 0;
}
int main()
{
// freopen("in.txt","r",stdin);
totleprm = getprm(20000);
u64 n;
u64 k;
u64 ans = 0;

while (scanf("%I64u%I64u",&n,&k)!=EOF)
{
u64 ans = kThPrim(n,k);
printf("%I64u\n",ans);
}
return 0;

}
```

Followed by: