| Time Limit: 10000MS | Memory Limit: Unknown | 64bit IO Format: %lld & %llu |
Description
|
B |
Race to 1 Input: Standard Input Output: Standard Output |
Dilu have learned a new thing about integers, which is - any positive integer greater than 1 can be divided by at least one prime number less than or equal to that number. So, he is now playing with this property. He selects a number N. And he calls this D.
In each turn he randomly chooses a prime number less than or equal to D. If D is divisible by the prime number then he divides D by the prime number to obtain new D. Otherwise he keeps the old D. He repeats this procedure until D becomes 1. What is the expected number of moves required for N to become 1.
[We say that an integer is said to be prime if its divisible by exactly two different integers. So, 1 is not a prime, by definition. List of first few primes are 2, 3, 5, 7, 11, ]
Input
Input will start with an integer T (T <= 1000), which indicates the number of test cases. Each of the next T lines will contain one integer N (1 <= N <= 1000000).
Output
For each test case output a single line giving the case number followed by the expected number of turn required. Errors up to 1e-6 will be accepted.
Sample Input Output for Sample Input
|
3 1 3 13 |
Case 1: 0.0000000000 Case 2: 2.0000000000 Case 3: 6.0000000000 |
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
#define maxn 1000010
int a[maxn]={},b[maxn],t;
void init()
{
long long i,j;
t=;
for(i=;i<maxn;i++)
{
if(!a[i])
{
b[t++]=i;
j=i*i;
while(j<maxn)
{
a[j]=;
j+=i;
}
}
}
}
double fun(int n)
{
double sum=;
int i,x=,y=;
for(i=;b[i]<=n&&i<t;i++)
{
x++;
if(n%b[i]==)
{
y++;
sum+=fun(n/b[i]);
}
}
sum+=x;
if(y)
return sum/y;
else return sum;
}
int main()
{
init();
int i,j,t,n;
scanf("%d",&t);
for(i=;i<=t;i++)
{
scanf("%d",&n);
printf("Case %d: %lf\n",i,fun(n));
}
}