Timus - 1860, Fiborial, Time Limit Exceed, any better idea?

[doctorlai]

http://acm.timus.ru/problem.aspx?space=1&num=1860

Code: Select all

#include <iostream>
using namespace std;

int n;
const int maxn = 1000000;
//const int maxn=20;

int a[maxn];
int b[maxn];
int c[maxn];

void copyarr(int *src, int *dest)
{
   for (int i = 0; i <= n; i ++)
   {
      dest[i] = src[i];
   }
}

void addarr(int *src1, int *src2, int *dest)
{
   for (int i = 0; i <= n; i ++)
   {
      dest[i] = src1[i] + src2[i];
   }   
}

int count(int *src)
{
   int cnt = 1;
   for (int i = 2; i <= n; i ++)
   {
      cnt *= (src[i] + 1);
      cnt %= 1000000007;
   }
   return (cnt);
}

void fac(int *src, int j)
{
   int p = 1, st = 1;
   while (j > 1)
   {
      p += st;
      while (j % p == 0)
      {   
         src[p] ++;         
         j /= p;
      }
      if (p == 2)
      {
         p = 1;
         st = 2;
      }
   }
}

int main()
{
   int i, cnt;
   cin >> n;
   for (i = 0; i <= n; i ++)
   {
      a[i] = 0; b[i] = 0; c[i] = 0;
   }
   for (i = 2; i <= n; i ++)
   {
      addarr(a, b, c);
      fac(c, i);
      copyarr(b, a);
      copyarr(c, b);
   }
   cout << count(c) << endl;
   return (0);
}

There must be some math optimization reduction based on number theory.

[dfy]

Short summary of your algorithm would be nice, it's a bit hard to crawl through that.
Are you using that 10^9 + 7 is prime? That helps.

[doctorlai]

Short summary of your algorithm would be nice, it's a bit hard to crawl through that.
Are you using that 10^9 + 7 is prime? That helps.

My idea is very easy.
1. compute the F every step
2. compute its factor number
3. use long arithmetic to store the result

of course this is very naive.

[dfy]

Ah, silly me. I totally misread the question ! I think I have an idea that should get AC, but it's not very refined (certainly won't get sub-100ms like the top-rated solutions). I'll try tonight...

[doctorlai]

Ah, silly me. I totally misread the question ! I think I have an idea that should get AC, but it's not very refined (certainly won't get sub-100ms like the top-rated solutions). I'll try tonight...

Thanks...
I am not very good at number theory, maybe there are facts that we can simplify the computation.

[dfy]

As a first hint: Any kind of trial division code should have something like a square root in it (well, implement it the other way round to avoid floating point, but the idea is the same), otherwise you're doing way too much work .

edit: ... but that's not enough to get more tests accepted. Even with that check, and using memcpy instead of your arraycopy, your approach has TL5.

edit 2: In fact, as it stands that code has no way of getting AC, simply because you're doing LOADS of unneccessary work. Think about it, when n=10^6, you need 10^12 additions alone to do all your addarray stuff. That alone will take at least 10 minutes, and then you haven't done anything else at all!

[doctorlai]

As a first hint: Any kind of trial division code should have something like a square root in it (well, implement it the other way round to avoid floating point, but the idea is the same), otherwise you're doing way too much work .

edit: ... but that's not enough to get more tests accepted. Even with that check, and using memcpy instead of your arraycopy, your approach has TL5.

edit 2: In fact, as it stands that code has no way of getting AC, simply because you're doing LOADS of unneccessary work. Think about it, when n=10^6, you need 10^12 additions alone to do all your addarray stuff. That alone will take at least 10 minutes, and then you haven't done anything else at all!

Great hints, I 'll try later.

[doctorlai]

As a first hint: Any kind of trial division code should have something like a square root in it (well, implement it the other way round to avoid floating point, but the idea is the same), otherwise you're doing way too much work .

edit: ... but that's not enough to get more tests accepted. Even with that check, and using memcpy instead of your arraycopy, your approach has TL5.

edit 2: In fact, as it stands that code has no way of getting AC, simply because you're doing LOADS of unneccessary work. Think about it, when n=10^6, you need 10^12 additions alone to do all your addarray stuff. That alone will take at least 10 minutes, and then you haven't done anything else at all!

Have you ACed the problem ?