Lightoj 1038 - Race to 1 Again

Formualte the recurrance when you have the same state repeating over and over multiple times. move the same states to one side by pokkhantor and formulate a new recurrance relation.
E(n) = 1 + 1/D * Sum( n/di )  i=2 to D  + 1/D * E(n)
Formulate and Solve it to find the recurrance of E(n). Here D is the number of divisors of n;
 

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define sci(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define MOD 100007

vector<int>divisors[MOD];

void divs()
{
    FOR(i,2,MOD)
    {
        for(int j=i; j<=MOD; j+=i) divisors[j].pb(i);
    }
}

double dp[MOD];
bool vis[MOD];

double solve(int n)
{
    if(n==1) return 0.0;

    if(vis[n]) return dp[n];
    vis[n] = 1;

    dp[n] = 0.0;

    int cnt = SZ(divisors[n])+1;

    REP(i,SZ(divisors[n]))
    {
        dp[n] += solve(n/divisors[n][i]);
    }

    return dp[n] = (cnt + dp[n]) * (double) (1.0/(cnt - 1.0));
}


int main()
{
    divs();

    int t,cs=0,n;
    scanf("%d", &t);
    while(t--)
    {
        mem(vis,0);
        scanf("%d", &n);
        double res = solve(n);
        printf("Case %d: %f\n", ++cs, res);
    }
    return 0;
}