lightoj1038

CODE

#include <iostream>
#include <iomanip>
using namespace std;
double dp[100005];
int ncase;
int cnt;
int main()
{
        int t;
        cin >> t;
        dp[1]=0;
        for(int i=2;i<=100000;i++)
        {
                double sum=0;
                int num=0;
                for(int j=1;j*j<=i;j++)
                {
                        if(i%j==0)
                        {
                                num++;
                                sum+=dp[j];
                                if(i/j!=j)
                                {
                                        num++;
                                        sum+=dp[i/j];
                                }
                        }
                }
                sum+=num;
                sum/=num-1;
                dp[i]=sum;
        }
        while(t--)
        {
                int n;
                cin >> n;
                cout <<fixed<<setprecision(10)<<"Case "<<++ncase<<": "<<dp[n]<<endl;
        }
        return 0;
}