10820 - Send a Table

[mido]

Seems literally everyone was able to solve A...any hints would be appreciated....

[marian]

http://mathworld.wolfram.com/TotientFunction.html

[sumankar]

Can someone give output for the following :

Code: Select all

1
100
1000
10000
50000

My outputs are:

Code: Select all

1
5647
550769
54866397
3089251479

Regards,
Suman.

[Observer]

Your output is not correct. However, since I haven't got my code with me now, I can't give you the correct one...

The output for 50000 should be something like 15xxxxxxxx.

P.S. about 30% of submissions to this task is contributed my me~

[Cho]

Can someone give output for the following :

Code: Select all

1
100
1000
10000
50000

Correct output:

Code: Select all

1
6087
608383
60794971
1519848527

[sumankar]

Cho and Observer,

Thanks a zillion tonnes, i owe that 6th place to you guys.

I forgot

premature optimization is the root of all evil
- Knuth


regards,
Suman.

[Cosmin.ro]

You can do it with an algo similar to the sieve of Eratosthenes.

[sumankar]

Cosmin.ro

If that was for me, my answer would be - that's exactly what I did

Regards,
Suman

[Observer]

Tried 20 more times and get down to 0.00.008... Dunno how to optimize it anymore. Maybe some look-up tables? (Dun even know what to put in the table)

P.S. sumankar, sorry if my reply wasn't that useful...
P.P.S. Lawrence (..) has just achieved 0.00.000! ho ging ah~~~

[sumankar]

Tried 20 more times and get down to 0.00.008... Dunno how to optimize it anymore. Maybe some look-up tables? (Dun even know what to put in the table)

Look - up Tables -huh?Have the totient functions calculated for all n
and calculating totient functions would mean the answers can be calculated easily - store them in a table and go on printf'ing happily ever after.

P.S. sumankar, sorry if my reply wasn't that useful...

No it was, believe me.

P.P.S. Lawrence (..) has just achieved 0.00.000! ho ging ah~~~

Let's hope he comes down and explains here ...

Regards,
Suman.

[Observer]

Look - up Tables -huh?Have the totient functions calculated for all n and calculating totient functions would mean the answers can be calculated easily - store them in a table and go on printf'ing happily ever after.

Please try it then ~

Don't think ..'s doing this way though.

- EDIT -

P.S. I wonder what other PASCAL programmers are using. My PASCAL solution can get this time:
http://acm.uva.es/cgi-bin/OnlineJudge?S ... 42:1.00:60::
which is about ten times faster than the current fastest PASCAL solution in ranklist... And I haven't used any precalculation

[mido]

Forgot to say this: Thanks, marian

[AndyGee]

Its my first program in C++.
I run the following code on the VC++, and it was ok.
But the judge give me "Compile Error".
Can anyone help me?

Code: Select all

#include <stdio.h>
//using namespace std; 

int p[50001];
int pc[50001];
long f[50001];



void PrepareArray()
{
   long j;
   for (long i = 2;  i <= 50000; i++) {
      pc[i] = pc[i-1];
		if (p[i]) continue;
      pc[i] = pc[i] + 1;
      j = 2 * i;
      for (; j <= 50000; j=j+i) p[j]++;
      
   }
   
}

void main()
{
   
   for (long i = 1; i <= 50000 ; i++) p[i] = 0;
   for (i = 1; i <= 50000 ; i++) pc[i] = 0;
   for (i = 1; i <= 50000 ; i++) f[i] = 0;
   PrepareArray();

   long max = 1;
   f[1] = 1;
   int N = 0;
   while (scanf("%d\n",&N)==1){
	   if (N > max) {
		  for (i = max + 1; i <= N; i++)
			 if (p[i]) { f[i] = f[i-1] + (pc[i] - p[i] + 1)*2; }
			 else { f[i] = f[i-1] + (i - 1) * 2; }
		  max = N;
	   }
      printf("%d\n",f[N]);
   }

}

[AndyGee]

I try to use

Code: Select all

#include <cstdio>
using namespace std; 

but CE again

[sohel]

Consider this part of your code:

Code: Select all

for (long i = 1; i <= 50000 ; i++) p[i] = 0; 
   for (i = 1; i <= 50000 ; i++) pc[i] = 0; 

The scope of i is only within the first for()..
.. for the second for, i has not been declared..

change it to something like

Code: Select all

long i;
for (i = 1; i <= 50000 ; i++) p[i] = 0; 
   for (i = 1; i <= 50000 ; i++) pc[i] = 0; 

And that should avoid CE...