Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator