Lightoj 1038 - Race to 1 Again

http://lightoj.com/volume_showproblem.php?problem=1038

1. #include <bits/stdc++.h>
2. using namespace std;
3. vector<int> v[100006];
4. double dp[100005];
5. int vis[100005];
6. void preprocess(){
7.     for(int i = 1; i <100006; i++){
8.         for(int j = i; j <100006; j+= i){
9.             v[j].push_back(i);
10.         }
11.     }
12.     /*
13.     for(int i = 1; i <=100; i++){
14.         for(int j = 0; j <v[i].size(); j++){
15.             cout<<v[i][j]<<" ";
16.         }
17.         cout<<endl;
18.     }
19.     */
20. }
21.  
22. double DP(int n){
23.     if(vis[n]) return dp[n];
24.     if(v[n].size() == 2) return 2.00;
25.     double sum= 0.00;
26.     for(int i = 0; i <v[n].size()-1; i++){
27.         sum+= 1.00+DP(v[n][i]);
28.  
29.     }
30.     sum+= 1.00;
31.     sum/= (v[n].size()-1)*1.00;
32.     vis[n] = 1;
33.     return dp[n] = sum;
34. }
35. int main(){
36.     preprocess();
37.     dp[1] = 0.00;
38.     dp[2] = 2.00;
39.     vis[1] = 1;
40.     vis[2] = 1;
41.     int ts;
42.     cin>>ts;
43.     for(int k = 1; k <= ts; k++){
44.     int number;
45.     cin>>number;
46.     printf("Case %d: %10lf\n",k,DP(number));
47.     }
48.     return 0;
49. }