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

600多ms 还能怎么优化??

Posted by first at 2006-02-26 00:35:21 on Problem 2478
#include <cstdio>
int n;
const int MAX = 1000001;
int sushu[200];
bool comp[1000];
__int64 phy[MAX];
__int64 tab[MAX];
__int64 ans;
int c = 0;

int main()
{
    phy[1] = 1;
	tab[1] = 0;
	sushu[0] = 2;
	int i, j;    
	for(i = 2; i < 1000; i++)
	{
		if(!comp[i])
		{
			for(j = i * 2; j < 1000; j += i)
			{
				comp[j] = 1;
			}
		}
	}
	for(i = 2; i < 1000; i++)
	{
		if(!comp[i])
		{
			sushu[c ++] = i;
		}
	} 
	for(j = 2; j < MAX; j ++)
	{
		for(i = 0; i < c ;i ++)
		{
			int k = j/sushu[i];
			if(j%sushu[i] == 0)
			{
				if(k%sushu[i] == 0)
					phy[j] = phy[k]*sushu[i];
				else
					phy[j] = phy[k]*(sushu[i] - 1);
				break;
			}
		}
		if(i == c)
			phy[j] = j - 1;
	}

	for(i = 2; i < MAX; i ++)
		tab[i] = tab[i - 1] + phy[i];
	while(scanf("%d", &n) && n)
	{		
		printf("%I64d\n", tab[n]);	
	}	
	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