I learnt some combinatorics, and tried my best
#include <iostream>
#include <deque>
using namespace std;
int p[127]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709};
int sieve[500001];
class dynamite{
int counter, current, period,start, end, retval;
public:
void set(int s,int e,int p){
start = s;
end = e;
period= p;
counter=0;
current = start;
}
int gen(){
retval = current;
counter++;
if (counter>=period){
counter=0;
current++;
if (current>end)
current=start;
}
return retval;
}
};
main(){
int n,test,i,isprime,sum=0,cnum,cpow,period;
int firstmatch;
float test2;
deque<int> pfacs,powers;
cin >> n;
// make the sieve
for (int i=2;i<=709;i++)
sieve[i]=0;
for (int i=710;i<=500000;i++)
sieve[i]=1;
for (int i=0;i<127;i++)
sieve[p[i]]=1;
// extend the sieve
for (i=0;i<127;i++){
firstmatch=500001;
for(int j=710;j<=500000;j++){
if (j%p[i]==0){
firstmatch=j;
break;
}
}
while (firstmatch<=500000){
sieve[firstmatch]=0;
firstmatch+=p[i];
}
//all factors of p[] made zero
// now sieve has 1 for primes till 500000
}
while (n--){
cin >> test;
// final combinatorial calculation
sum=1;
// build list of prime factors and corresponding powers
for (i=2;i<=test;i++){
if (sieve[i]){
if (test%i == 0){
pfacs.push_back(i);
cpow=0; cnum=test;
while(cnum%i == 0){
cnum = cnum/i;
cpow++;
}
powers.push_back(cpow);
}
}
}
sum=0;
period=1;
// decide number of dynamites
if (1){
dynamite d[pfacs.size()];
d[0].set(0,powers[0],period);
for (int i=1;i<pfacs.size();i++){
period*=powers[i-1]+1;
d[i].set(0,powers[i],period);
}
int lim=period*(powers[powers.size()-1]+1);
int prod;
for (int i=0;i<lim;i++){
prod = 1;
for (int j=0;j<pfacs.size();j++){
int p1=d[j].gen();
for (int x=0;x<p1;x++)
prod *=pfacs[j];
}
sum+=prod;
}
cout <<sum-test <<endl;
}
pfacs.clear();
powers.clear();
}
}
all i get is a TLE !!!
but for input of
1
500000 its pretty fast !