10820 - Send a Table

[sandy007smarty]

Ac but not satisfied with the time.
I used medv's function to calculate the no. of relative primes for a number i. and then
result=result[i-1]*2*no_of_relative_primes(i);
I precalculated 1 to 50,000 before scanning any input.
Then i just print the result[n] for each input n.
But it took 0.277 seconds. How do i improve the time?

[sandy007smarty]

AC in 0.12 but still not satisfied.
I am now not using medv's function but a variant of sieve.
I calculate totient function for all n from 1 to 50,000.
Then I calculate all answers from 1 to 50,000.
Then i just scan and print the apropriate answer from the array.

Please suggest a better method. How to get 0.002?

[sclo]

Either use a faster sieve, or just compute result+=result[i-1], and for each input n, output result[n]*2-1

[sandy007smarty]

@sclo:
1. Is their some faster sieve algo? Can you provide some links?
2. Calculating result+=result[i-1]+result<<1 and just printing result[n] seems similar to what you suggest. I can't see what computational advantages your method has.

Below is my code for calculating totient using sieve:-

Code: Select all

for(i=1;i<50001;i++)
     nrp[i]=i;
for(i=2;i<50001;i++)
     if(nrp[i]==i)
     {
          nrp[i]--;
          for(j=i<<1;j<=50000;j+=i)
               nrp[j]=nrp[j]*(i-1)/i;
     }

And this is my code for calculating result:-

Code: Select all

last = ans[1] = 1;
for(i=2;i<=50000;i++)
      last = ans[i] = last + (nrp[i]<<1); // variable last is used instead of ans[i-1] just to save a few memory accesses

I would appreciate if you could suggest some ways to improve above functions.

[panhantao]

@sclo:
1. Is their some faster sieve algo? Can you provide some links?
2. Calculating result+=result[i-1]+result<<1 and just printing result[n] seems similar to what you suggest. I can't see what computational advantages your method has.

Below is my code for calculating totient using sieve:-

Code: Select all

for(i=1;i<50001;i++)
     nrp[i]=i;
for(i=2;i<50001;i++)
     if(nrp[i]==i)
     {
          nrp[i]--;
          for(j=i<<1;j<=50000;j+=i)
               nrp[j]=nrp[j]*(i-1)/i;
     }

And this is my code for calculating result:-

Code: Select all

last = ans[1] = 1;
for(i=2;i<=50000;i++)
      last = ans[i] = last + (nrp[i]<<1); // variable last is used instead of ans[i-1] just to save a few memory accesses

I would appreciate if you could suggest some ways to improve above functions.

well,actually i don't quite understand your codes , but i can share my pre-calculating codes, which i used getting ac in 0.012sec

Code: Select all

const int MAXN = 50005;
bool isPrime[MAXN+5];
int phi[MAXN],farey[MAXN];

void init()
{
	// generate prime numbers
	memset(isPrime,true,sizeof(isPrime)); 
	isPrime[0] = isPrime[1] = false;
	for(int i = 2; i*i <= MAXN; i ++)
		if(isPrime[i])
			for(int j = i; j*i <= MAXN; j ++)
				isPrime[i*j] = false;
	
	// because phi(i) = i*(1-p1/p1)*...*(1-pk/pk), you can generate the phi[] array similar to the way we generate prime numbers
	for(int i = 1; i <= MAXN; i ++) phi[i] = i;
	for(int i = 2; i <= MAXN; i ++)
		if(isPrime[i])
			for(int j = i; j <= MAXN; j += i)
				phi[j] = phi[j]/i * (i-1);
	
	// sum up phi[i] to farey[i]. obiously, the answer for a given N would be (2*farey[N]-1).
	farey[1] = 1;
	for(int i = 2; i <= MAXN; i ++)
		farey[i] = farey[i-1] + phi[i];
}