TLE: UVa 13279 Divisors

Revision en1, by sajalhsn13, 2018-05-18 11:01:27

Hello,

I am trying to solve this problem and getting TLE, and I think my code is the best I can do. Please help me solve the problem by any efficient idea or optimizing my code:

#include <bits/stdc++.h>

using namespace std;

#define MX 5000005
#define M 100000007
#define LL long long
#define dbg(x) cout<<#x<<" = "<<x<<"\n"

int n;
LL cnt[MX];
int b[MX];

int main(){
    while(cin>>n){
        if(n==0) break;
        memset(b,0,sizeof(b));
        for(int i=n,v=1;i>1;i--,v++){
            cnt[i]=v;
        }
        for(int i=2;i<=n;i++){
            if(b[i]==0){
                for(int j=i*2;j<=n;j+=i){
                    b[j]=1;
                    int t=j;
                    int div=0;
                    while(t%i==0){
                        div++;
                        t/=i;
                    }
                    cnt[i]+=cnt[j]*div;
                }
            }
        }
        LL ans=1;
        for(int i=2;i<=n;i++){
            if(b[i]==0){
                ans=(ans*(cnt[i]+1))%M;
            }
        }
        printf("%lld\n",ans);
    }
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English sajalhsn13 2018-05-18 11:02:07 6 Tiny change: ' the best I can do.' -> ' the best thing I can do.'
en1 English sajalhsn13 2018-05-18 11:01:27 1232 Initial revision (published)