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

Re:我一直超时....大哥们能不能发我一份代码啊?

Posted by first at 2006-03-26 23:34:45 on Problem 2773
In Reply To:我一直超时....大哥们能不能发我一份代码啊? Posted by:Sempr at 2006-03-26 23:33:25
#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