codeworrior's blog

recurrence
By codeworrior, 14 years ago, In English
A recurrence is defined as
    F(x)=summation { F(y) : y is divisor of x and y!=x }
    F(1)=1
e.g. F(12)=F(1)+F(2)+F(3)+F(4)+F(6)=F(1)+F(2)+F(3)+F(1)+F(2)+F(1)+F(2)+F(3)=8

1 <  x  < 2^31
how can i solve this recurrence relation??
  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Either standard DP or memoized recursion.
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
Then, just prime factorize.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Sorry, here is my post.

so you can write something like this:

#include <cstdio>
#include <map>
#include <math.h>
using namespace std;

map <int,int> m;
int n;

int rec ( int n )
{
    if ( m.find( n ) != m.end() )
        return m[n];
    int lim = sqrt(double(n));
    int res = 0;
    for ( int i = 1; i <= lim; ++i )
    {
        if ( n % i == 0 )
        {
            res += rec ( i );
            if ( i*i != n && i != 1 )
                res += rec ( n / i );
        }
    }
    m[n] = res;
    return res;
}

int main ()
{
    m[1]=1;
    scanf("%d", &n);
    printf("%d", rec(n) );
    return 0;
}
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    got it ACed..thanx...i never believed it could work.. i thought we have to work out some formula to get it ACed ..thanx..
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why not?

      We got about 1000 ( (10^9)^(1/3) ) divisors, make operations (find, add) with Map by log2(10^9) (it's about 30), and with 5000 test cases we got smthng like 1000*30*5000 = 150 000 000 operations (if there is no issue).

      You're welcome. :)

      By the way, where did you find that problem? (link)

      → Reply
      • 14 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it
        yes but we dont know what those divisors are..so we have to loop through the sqrt(n) values to get to those divisors...so it should be 46000*30*5000=6900000000(unless we find some way in which we can get divisor in O(n^1/3) if its possible then enlighten me :)  ..
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Anyway my solutions passed. ;)
          And could you give a reference on a problem?
          → Reply
14 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
Note that F(1) occurs d(n)-1 times. Using similar idea, F(p) should occur d(n/p)-1 times (or something similar).

So, at the end, the answer is something like sum(d(n/p)-1) + d(n)-1 where sum is take over all prime divisors of n. Obviously, each of d's here can be found in constant time given that we have a prime factorization for n.

Any more question?
→ Reply
14 years ago, # |
  Vote: I like it +4 Vote: I do not like it
You are right; the conclusion I made was way too abrupt. I wonder if there exists a simple 'formula' to get this; my inclination is 'yes' but I have not worked it out in detail yet. I think it can be written as some expression of prime divisors of n. Any idea?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
i tried to get a formula for 2 days but could not get..i also think there could be some formula for it so i wasnt tying DP and in the end got AC using DP..but there should exist a formula and that would be a lot cooler way to do this problem..
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Some things to keep in mind:

    1) F(p^i) = 2^(i-1).
    2) F(n) = F(p1^i1 ... pk^ik)

    Using this, you may be able to reduce the computation time a bit. Right now, even getting F(p^i * q^j) seems non-trivial.

    At this point, I think I would definitely use DP here, after putting 1) in place [even more so in competition-type problem].
    → Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Have you tried generating some first values and then searching this sequence on oeis.org? I'm quite sure that you will find it there(if formula in closed form exists).
→ Reply