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??
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??
So maybe you can use recursive dynamic with balanced tree (for example map in C++ STL).
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;
}
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)
And could you give a reference on a problem?