Need tips to Optimizing my code

general
,
1

I am stuck in TLE in Divisor Summation
please help where I am going wrong
Solution link

2

This thread can help you.

3

Simply for each n find its divisors in O(sqrt(n))
https://www.codechef.com/viewsolution/34500416

4

brother can tell (give example) when this excute
for(int i=2;i<=sqrt(n);i++)
{
if(n%i==0)
{
sum+=i;
if(i!=n/i) <=== this one
sum+=n/i;
}
}

5

See when any no is perfect square then i will be to n/i if i=sqrt(n). So, not to add same no twice I have written that condition. Take n=9 and i=3

1 Like
6 
lli spf[MAX+1];

void sieve2(){ //smallest prime factor of N.

    loop(i,MAX+1) spf[i]=i;
    for(lli i=4;i<=MAX;i+=2) spf[i]=2;

    for(lli i=3; i*i<=MAX; i++){
        if (spf[i] == i){
            for (int j=i*i; j<=MAX; j+=i)
                if (spf[j]==j) //marking spf[j] if it is not previously marked
                    spf[j] = i;
        }
    }
}

lli tfactor[MAX+1];
lli sumfactor[MAX+1];
void sieve4(){ // totalfactor and sum_of_all_factors
    // n = (a^p)*(b^q)*(c^r)....
    // totalfactors = (p+1)*(q+1)*(r+1)...
    // sumoffactors =  [(a^(p+1)-1)/(a-1))]*[(b^(q+1)-1)/(b-1))]*[(c^(r+1)-1)/(c-1))]....
    sieve2();
    tfactor[1] = sumfactor[1] =1;
    for(lli i=2;i<=MAX;i++){
        lli mspf = spf[i];
        lli prim = mspf;
        lli temp = i;
        lli cnt=0;
        while(temp%mspf==0){
            temp/=mspf;
            cnt+=1;
            prim = prim*mspf;
        }
        tfactor[i] = (cnt+1) * tfactor[temp];
        sumfactor[i] = (prim -1)/(mspf-1) * sumfactor[temp];
     }
}
int main(){
fastio
lli t=1;
sieve4();
cin>>t;
while(t--) {
    lli n;
    cin>>n;
    cout<<sumfactor[n]-n<<endl;
  }
return 0;
}
7

brother can you explain me the logic

8

Please format your codes

9

Read my comment in sieve4 function :slight_smile:

10

sorry bro but what is MAX??

11

@codedirector usually a safe number, which is greater than the input constraints.
like if you are asked to create an array of 10 elements than to be at safe usually people create a variable or define as:
int MAX = 15
or
#define MAX 15
so here MAX represent the maximum value that can be provided in the input

12

MAX is Upper limit in this 500001

Here my AC solution : CodeChef: Practical coding for everyone

13

thanks brother as I don’t have idea about it.

14

bro remove extra code.
I think you have paste all your code on a single page.

15

That’s my way …BTW i gave u main code in above comment :slight_smile:

16

@codedirector “extra code” isn’t what @ssrivastava990 is using.
To see what is “extra code” check this : CodeChef: Practical coding for everyone .
I actually bookmarked this to copy templates in future.

17

Man around 2k lines :scream: :scream:

1 Like