10820 - Send a Table

AndyGee · Post by **AndyGee** » Wed Mar 16, 2005 12:22 pm

Thanks a lot!

mikeblas · Post by **mikeblas** » 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

AndyGee · Post by **AndyGee** » Sun Mar 20, 2005 8:10 am

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

ibrahim · Post by **ibrahim** » Fri Aug 19, 2005 1:04 pm

Critical I/O please.

Martin Macko · Post by **Martin Macko** » Fri Aug 19, 2005 1:13 pm

An input:

Code: Select all

My AC's output:

Code: Select all

nymo · Post by **nymo** » 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 )?

Ryan Pai · Post by **Ryan Pai** » 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.

nymo · Post by **nymo** » 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 ...

xlvector · Post by **xlvector** » 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

medv · Post by **medv** » 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.

Observer · Post by **Observer** » 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?

Krzysztof Duleba · Post by **Krzysztof Duleba** » 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.

Observer · Post by **Observer** » 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

)

Krzysztof Duleba · Post by **Krzysztof Duleba** » Thu Jan 05, 2006 4:48 pm

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

Observer · Post by **Observer** » 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