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 563150913 at 2010-09-26 22:55:26 on Problem 2773
#include<stdio.h>
__int64 gcd(__int64 a , __int64 b)
{
if(b == 0)
   return a ;
else
{
   return gcd(b,a % b );
}
}
__int64 save[1000001];
int main()
{
__int64 m = 0 , k = 0 ;
while(scanf("%d%d", &m ,&k)==2 )
{
   __int64 cnt = 0 , i ;
   int j = 0 ;
   int mark = 0 ;
   for( i = 1; i <= m ; i++)
   {
    if( gcd(m,i) == 1 )
    {
     cnt++;
     save[j++] = i ;
    }
    if( cnt == k)
    {
     mark = 1 ;
       printf("%d\n", i);
     break;
    }
   }
   if( mark != 1)//处理计算个数要输出的互质数……
   {
    int p = k/cnt ;
    if( k % cnt == 0)//当个数整除的时候要减一……
    {
     p -- ;
    }
    printf("%I64d\n",save[k - p * cnt - 1] + p*m);
   }
}
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