Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

呵呵，献丑了哦，直接拿下午TLE的改的，TLE得我整个contest都没心情做了

Posted by frkstyc at 2005-07-14 00:39:01 on Problem 2478
In Reply To:不要那么大火气：）你可以给我看看你代码吗？ Posted by:magic_pig at 2005-07-14 00:36:02

#include <stdio.h>
		 
int phi[1000001];
int comp[1000001];
int prime[1000], primes;
__int64 tab[1000001];

void eratosthenes(void)
{
	int i, j;
	for(i = 2; i < 1000; i++)
	{
		if(!comp[i])
		{
			for(j = i * 2; j <= 1000000; j += i)
			{
				comp[j] = 1;
			}
		}
	}
	for(i = 2; i < 1100; i++)
	{
		if(!comp[i])
		{
			prime[primes++] = i;
		}
	}
}

int main(void)
{
	int i, j;
	eratosthenes();
	for(i = 2; i <= 1000000; i++)
	{
		phi[i] = i;
		if(comp[i])
		{
			int p = i;
			if((p & 1) == 0)
			{
				phi[i] >>= 1;
				do
				{
					p >>= 1;
				}
				while((p & 1) == 0);
			}
			for(j = 1; prime[j] * prime[j] <= p; j++)
			{
				int t = prime[j];
				if(p % t == 0)
				{
					phi[i] = phi[i] / t * (t - 1);
					for(;;)
					{
						int s = p / t;
						if(s * t == p)
						{
							p = s;
						}
						else
						{
							break;
						}
					}
				}
			}
			if(p > 1)
			{
				phi[i] = phi[i] / p * (p - 1);
			}
		}
		else
		{
			phi[i]--;
		}
		tab[i] = tab[i - 1] + phi[i];
	}
	for(;;)
	{
		int n;
		scanf("%d", &n);
		if(n == 0)
		{
			break;
		}
		printf("%I64d\n", tab[n]);
	}
	return 0;
}

Followed by:

其实是你算法问题。。 (1380) magic_pig 2005-07-14 00:42:57
- 算了算了，不吵了……我再想办法刷一下 (0) frkstyc 2005-07-14 00:45:14
  - 如果有兴趣，我可以发标程给你看看，Euler函数利用的时候有点dp的技巧：） (0) magic_pig 2005-07-14 00:46:14
    - 这个好啊；btw，是不是利用前面算出来的小的？ (0) frkstyc 2005-07-14 00:47:29
      - 是的。所以这题你们超时，很大原因就是算法问题：） (0) magic_pig 2005-07-14 00:48:37
        所有contest的A题都会令我头疼…… (0) frkstyc 2005-07-14 00:50:24
      - 已经发了：） (0) magic_pig 2005-07-14 00:50:03
    - 我也要啊，我一直不了解这里怎么用dp的技巧 (25) Washington 2005-07-14 01:20:23
      - Re:我也要啊，我一直不了解这里怎么用dp的技巧 (32) Washington 2005-07-14 01:23:20
      - 发到了你站内邮箱。希望对你有启发。 (29) magic_pig 2005-07-14 10:21:09
        magic_pig我也要标程，发我站内邮箱吧！3X (0) animate 2005-07-14 17:54:30
        Re:magic_pig我也要标程,发到我站内的邮箱吧!!!!!!!3KS (0) ook 2005-07-14 18:41:13
    - Re:如果有兴趣，我可以发标程给你看看，Euler函数利用的时候有点dp的技巧：） (11) xl 2005-09-21 15:37:57

Post your reply here:

User ID:
Password:
Title:

Content:

> #include <stdio.h>
> 		 
> int phi[1000001];
> int comp[1000001];
> int prime[1000], primes;
> __int64 tab[1000001];
> 
> void eratosthenes(void)
> {
> 	int i, j;
> 	for(i = 2; i < 1000; i++)
> 	{
> 		if(!comp[i])
> 		{
> 			for(j = i * 2; j <= 1000000; j += i)
> 			{
> 				comp[j] = 1;
> 			}
> 		}
> 	}
> 	for(i = 2; i < 1100; i++)
> 	{
> 		if(!comp[i])
> 		{
> 			prime[primes++] = i;
> 		}
> 	}
> }
> 
> int main(void)
> {
> 	int i, j;
> 	eratosthenes();
> 	for(i = 2; i <= 1000000; i++)
> 	{
> 		phi[i] = i;
> 		if(comp[i])
> 		{
> 			int p = i;
> 			if((p & 1) == 0)
> 			{
> 				phi[i] >>= 1;
> 				do
> 				{
> 					p >>= 1;
> 				}
> 				while((p & 1) == 0);
> 			}
> 			for(j = 1; prime[j] * prime[j] <= p; j++)
> 			{
> 				int t = prime[j];
> 				if(p % t == 0)
> 				{
> 					phi[i] = phi[i] / t * (t - 1);
> 					for(;;)
> 					{
> 						int s = p / t;
> 						if(s * t == p)
> 						{
> 							p = s;
> 						}
> 						else
> 						{
> 							break;
> 						}
> 					}
> 				}
> 			}
> 			if(p > 1)
> 			{
> 				phi[i] = phi[i] / p * (p - 1);
> 			}
> 		}
> 		else
> 		{
> 			phi[i]--;
> 		}
> 		tab[i] = tab[i - 1] + phi[i];
> 	}
> 	for(;;)
> 	{
> 		int n;
> 		scanf("%d", &n);
> 		if(n == 0)
> 		{
> 			break;
> 		}
> 		printf("%I64d\n", tab[n]);
> 	}
> 	return 0;
> }

Home Page Go Back To top