10820 - Send a Table

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sandy007smarty
New poster
Posts: 20
Joined: Thu Apr 20, 2006 6:55 pm
Location: Hyderabad
Contact:

Post by sandy007smarty » Thu May 25, 2006 9:17 pm

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
New poster
Posts: 20
Joined: Thu Apr 20, 2006 6:55 pm
Location: Hyderabad
Contact:

Post by sandy007smarty » Fri May 26, 2006 12:28 pm

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Sep 08, 2006 3:53 am

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

sandy007smarty
New poster
Posts: 20
Joined: Thu Apr 20, 2006 6:55 pm
Location: Hyderabad
Contact:

Post by sandy007smarty » Sun Apr 08, 2007 8:55 pm

@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
New poster
Posts: 2
Joined: Tue Aug 14, 2012 6:00 pm

Re:

Post by panhantao » Tue Aug 14, 2012 6:13 pm

sandy007smarty wrote:@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];
}

Post Reply

Return to “Volume 108 (10800-10899)”