 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| 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 | |||||||||
其实是你算法问题。。In Reply To:呵呵，献丑了哦，直接拿下午TLE的改的，TLE得我整个contest都没心情做了 Posted by:frkstyc at 2005-07-14 00:39:01 > #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:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
