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 frkstyc at 2006-03-26 23:36:10 on Problem 2773
In Reply To:Re:高手 mail 给 我学习一下吧, 我太菜了 Posted by:first at 2006-03-26 23:35:15
> #include <iostream>
> #include <cmath>
> using namespace std;
> int m, k, ftop;
> const int len = 1000001;
> bool ok[len];
> int fact[1000];
> int cand[len];
> int main()
> {
> 	    int i, j;
> 		while(cin >> m >> k)
> 		{
> 			memset(ok, false, m + 1);
> 			ftop = 0;
> 			int tm = m;
> 			int euler = m;
> 			const int t = sqrt(tm); 
> 			for (i=2; i<=t&&i<=tm; i++)
> 			{
> 				if (tm%i==0)  
> 				{
> 					fact[ftop++]=i;
> 					euler = euler/i*(i - 1);
> 					while (tm%i==0) tm/=i;
> 				}
> 			}
> 			if (tm > 1) 
> 			{
> 				fact[ftop++] = tm; 
> 				euler = euler/tm*(tm - 1);
> 			}			
> 			for(i = 0; i < ftop; i ++)
> 			{
> 				if(m%fact[i] == 0)
> 				for(j = fact[i]; j <= m ; j += fact[i])
> 						ok[j] = true;
> 			}  
> 			int loop = (k - 1)/euler;
> 			int index = 1 + (k - 1)%euler;
> 			int ct = 0;
> 			for(i = 1; i <= m; i ++)
> 			{
> 				if(!ok[i])
> 				{
> 					ct ++;
> 					if(ct == index)
> 						cout << i + loop*m << endl;
> 				}				
> 			}			
> 		}
> 		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