10820 - Send a Table

[Ryan Pai]

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]

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]

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]

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]

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]

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]

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]

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

[Observer]

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.

[sandy007smarty]

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]

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?

[sclo]

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

[sandy007smarty]

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

[panhantao]

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