OJ Board

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

Thanks a lot!

Posted: **Sun Mar 20, 2005 1:12 am**

Which version of VC++ are you using? In vC++ 2003, you can set your projects to use the strict rules for for variable scoping.

.B ekiM

Posted: **Sun Mar 20, 2005 8:10 am**

Now I use GCC 3.3.3 (cygwin special) and have no more problems...

Posted: **Fri Aug 19, 2005 1:04 pm**

Critical I/O please.

Posted: **Fri Aug 19, 2005 1:13 pm**

An input:

Code: Select all

My AC's output:

Code: Select all

Posted: **Sun Sep 18, 2005 4:49 pm**

I 've tried to solve this problem, but i am never passing time limit.

I tried something like this :

i. for 1 ... Jimmy had to precalculate 1 value namely (1, 1)
ii. for i = 2 .. N, number of precalculated value = precalculated value for (i-1) + (2*(no. of j(= 1..i-1) that are relatively prime to i))

I use prime factoring to find those j's.

Is there anything wrong with my algo.? or, else how can i make it faster(it is not passing the limit )?

Posted: **Sun Sep 18, 2005 5:29 pm**

The slow part is probably your factoring. If you are iterating up to the square root of i and using the totient function then I would think that would be fast enough.

You could always try to use a faster factoring method.

Posted: **Sun Sep 18, 2005 8:16 pm**

Dear Ryan pai,
Thanks a lot, I just got ACC

, now it takes 0.096sec(Now, i 've passed the limit...).

I use Euler's phi function just as you 've mentioned, my factoring was a bit okay, but to factor out the multiples of factors, I used something like sieve ... and for marking and unmarking, I use loops and memset() everytime ... I guess that was the bottleneck. Anyway, thanks a lot ...

Posted: **Thu Dec 29, 2005 2:42 pm**

I use totient function , but it still needs factoring,

I use this : if (m,n)=1， f(mn)=f(m)f(n)
but I find it cost time when I divide a numer m*n into m,n

can someone help me

Posted: **Wed Jan 04, 2006 2:05 pm**

To xlvector:
I think it's enough to evaluate f(n):

int f(int n)
{
int result = n;
for(int i=2;i*i <= n;i++)
{
if (n % i == 0) result -= result / i;
while (n % i == 0) n /= i;
}
if (n > 1) result -= result / n;
return result;
}

Then precompute all f(n), n=1,50000. And will get ACC.
Still wa - write me, I got acc.

Posted: **Thu Jan 05, 2006 7:59 am**

Hi,

If I remember correctly, I also used something like sieve...

I'm currently ranked #2 for this task. But I have no idea how 0.00.002 can be achieved.... Faster I/O?

Posted: **Thu Jan 05, 2006 1:29 pm**

Observer wrote:I'm currently ranked #2 for this task. But I have no idea how 0.00.002 can be achieved.... Faster I/O?

Now you're third

Faster I/O doesn't help here as the input is very small.

Posted: **Thu Jan 05, 2006 2:13 pm**

Krzysztof Duleba wrote:Now you're third

Good for you~ Don't want to improve my code, since I think it is now short (14 lines) and beautiful. (And the other reason is of course I don't know what I can improve

)

Posted: **Thu Jan 05, 2006 4:48 pm**

14 lines - that's pretty impressive. The sieve loop alone took me 21 lines.

Posted: **Thu Jan 05, 2006 5:15 pm**

okay, maybe not that impressive... One of the lines read:

Code: Select all

for (i=3;i<=223;i+=2) if (!fac[i]) for (s=i*i;s<=50000;s+=i<<1) fac[s]=i;

which is long, though I find no reason to break it into several lines.

OJ Board

10820 - Send a Table

10820 Send a Table

Re: 10820 Send a Table

I need to know how to deal with this ...

I also have time problem

Hint