OJ Board

Posted: **Sat Mar 05, 2005 9:25 pm**

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

Posted: **Sat Mar 05, 2005 11:53 pm**

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

Posted: **Wed Mar 09, 2005 6:37 am**

Can someone give output for the following :

My outputs are:

Code: Select all

Regards,
Suman.

Posted: **Wed Mar 09, 2005 6:39 am**

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~

Posted: **Wed Mar 09, 2005 8:20 am**

sumankar wrote:Can someone give output for the following :
Code: Select all
1
100
1000
10000
50000

Correct output:

Code: Select all

Posted: **Wed Mar 09, 2005 10:46 am**

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.

Posted: **Wed Mar 09, 2005 4:06 pm**

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

Posted: **Wed Mar 09, 2005 4:08 pm**

Cosmin.ro

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

Regards,
Suman

Posted: **Wed Mar 09, 2005 4:31 pm**

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~~~

Posted: **Thu Mar 10, 2005 6:21 am**

Observer wrote: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.

Posted: **Thu Mar 10, 2005 6:33 am**

sumankar wrote: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

Posted: **Sat Mar 12, 2005 6:27 pm**

Forgot to say this: Thanks, marian

Posted: **Wed Mar 16, 2005 11:41 am**

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]);
   }

}

Posted: **Wed Mar 16, 2005 11:44 am**

I try to use

Code: Select all

#include <cstdio>
using namespace std;

but CE again

Posted: **Wed Mar 16, 2005 12:00 pm**

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...

OJ Board

10820 - Send a Table

10820 - Send a Table

Compile Error C++ 10820

ooopsii daisy...