## 10820 - Send a Table

Moderator: Board moderators

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.
I'm always willing to help, if you do the same.
Ryan Pai
Learning poster

Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA

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 ...
nymo
Experienced poster

Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

### I also have time problem

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
xlvector
New poster

Posts: 11
Joined: Thu Dec 29, 2005 8:30 am

### Hint

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.
medv
Learning poster

Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

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?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Observer
Guru

Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

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.

Krzysztof Duleba
Guru

Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland

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 )
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Observer
Guru

Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

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

Krzysztof Duleba
Guru

Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland

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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Observer
Guru

Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

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[i]=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

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?
sandy007smarty
New poster

Posts: 20
Joined: Thu Apr 20, 2006 6:55 pm

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

Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm

@sclo:
1. Is their some faster sieve algo? Can you provide some links?
2. Calculating result[i]+=result[i-1]+result[i]<<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.
sandy007smarty
New poster

Posts: 20
Joined: Thu Apr 20, 2006 6:55 pm

### Re:

sandy007smarty wrote:@sclo:
1. Is their some faster sieve algo? Can you provide some links?
2. Calculating result[i]+=result[i-1]+result[i]<<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];}`
panhantao
New poster

Posts: 2
Joined: Tue Aug 14, 2012 6:00 pm

Previous