Do not use long long int unless it is necessary.They are very slow.
In this problem everything fits in int.
Do not use floor(sqrt(n)) inside a loop because each time the loop is run it would calculate the square root and that alone would cause TLE.Compute before and store it in a variable.
Also you can check the special condition outside the loop. 
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 !
i removed deques
reduced the code
still getting TLE
should i make the prime sieve faster ? as done in prime1 problem?
#include <iostream>
#include <math.h>
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];
main(){
int n,test,i,isprime,sum=0,cnum,cpow,term;
int firstmatch;
float test2;
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--){
scanf ("%d",&test);
// final combinatorial calculation
// build list of prime factors and corresponding powers
cnum=test;
sum=1;
for (i=2;i<=test && cnum>=2;i++){
if (sieve[i]){
if (test%i == 0){
cpow=0;
term=1;
while(cnum%i == 0){
cnum = cnum/i;
cpow++;
term += pow(i,cpow);
}
sum*=term;
}
}
}
printf ("%d\n",sum==test ? 1:sum-test);
}
return 0;
}
You are unnecessarily complicating the thing ... 
You can do that with a very small 15 line code 
The idea is as follows --
Let the number be n .. then let k = n/2 + 1 .
Now you need to run only a loop for 2 to k and also modify the value k in the loop . Don't Read Ahead if u want to think more.
To put plainly if (n%i) == 0 ,, then i and n/i both are divisors of n .
Also there can't be a divisor greater than k/i after each run , so we can change k to k/i.I Hope it Helps.
Best Regards,
Yash
i was trying prime factorization method
planetmath.org/encyclopedia/Form ... isors.html1
i still have a TLE, i need to do some paperwork
GSHHHHHH even this doesnt work...
I will give it a fresh thought tomorrow...
#include <iostream>
using namespace std;
main (){
int n,t,sum,k,i;
scanf ("%d",&n);
while (n--){
scanf ("%d",&t);
sum=1;
k=t/2 + 1;
i=2;
while (i<k){
if (t%i==0){
sum += i + t/i;
k=k/i;
}
i++;
}
printf ("%d\n",sum);
}
}
There are lots of input numbers so it would be possible to get TLE by your method.
You can compute sigma(k) for all k up to n in O(n*log(n)) time and using
O(n) memory (it was my original solution, it takes about 0.84 sec.), but also
in O(n*log(log(n))) time. And you can get probably a nice improvement, if
you use fread/fwrite for fast input/output, because there are large amount of
input/output in the program. [Note that the answer is sigma(n)-n if the input=n].
[quote="Robert Gerbicz"]
There are lots of input numbers so it would be possible to get TLE by your method.
/quote]
No, I got acc. in 1.3s using scanf,printf.
ya 1.3 sec i got... but i don't like it
can we somehow implement planetmath.org/encyclopedia/Form ... isors.html5
in a faster way! because this is a very direct approach.
I tried using that formula..
what I do is calculate and store all primes first.
Then check for the prime divisors of the input number.
which is pretty simple but unfortunately TLE
Can't think of any O(nlogn)approach to precalculate all values and store as Robert said (and too sleepy to think right now)...
if t is power of 2, sigma(t)-t = t-1
[code]if ( (t&(t-1))==0 ){
printf ("%d\n",t-1);
continue;
}[/code]i was hoping this would cut down on calculations and make prog faster, but still i get 1.3 sec. why doesn't this step optimize the processs ?
#include<stdio.h>
int main()
{
int N;
int n,count=0 , last,fac,i,k; // make it unsigned
scanf("%d",&N);
for (k = 0; k < N ; k++)
{
scanf("%d",&n);
count = 1;
last = n/2;
i = 2 ;
while(i < last)
{
if ((n%i)==0)
{
last=n/i;
count = count + i + last ;
}
i++;
}
if (--i == last ) count-=i;// If factors are same
printf("%d\n",count);
}
}
This too TLE . I have been cutting corners but no use. .
:([code][/code]You don't need to check upto n/2 .See previous posts in this thread and other threads related to this problem for hints.
var "last" is modified inside loop. It won't cross sqrt(n) .
Also I wanna know is there a faster algorithm ?
Thanks .
That did the job .
from 1 min 5 secs to 2 secs on my test case .
Also what is common practice to reduce I/O overhead in such problems (with Large amount of IO). I pretty much use scanf printf .
Can someone tell why my code doesn’t work? For the example test cases the output is
1
18446744073709551609
22
#include <stdio.h>
#include <math.h>
size_t divsum(size_t n);
int main(void)
{
int t;
size_t n;
scanf("%d", &t);
while (t--) {
scanf("%lu", &n);
printf("%lu\n", divsum(n));
}
return 0;
}
size_t divsum(size_t n)
{
size_t sum = 1, exp, original = n;
for (size_t p = 2; p <= ceil(sqrt(original)); p++) {
exp = 0;
if (n % p == 0) {
while (n % p == 0) {
exp++;
n /= p;
}
sum *= (pow(p, exp + 1) - 1) / (p - 1);
}
}
return sum - original;
}