sajalhsn13's blog

TLE: UVa 13279 Divisors
By sajalhsn13, history, 7 years ago, In English

Hello,

I am trying to solve this problem and getting TLE, and I think my code is the best thing 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);
    }
}
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Instead of doing sieve every time, just precalculate primes in the outside and put them into one array. It should work in given time limit.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    got TLE

    #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 p[MX];
vector<int> prime;

void getPrime(){
    p[0]=p[1]=1;
    for(int i=4;i<MX;i+=2){
        p[i]=1;
    }
    for(int i=3;i*i<MX;i+=2){
        if(p[i]==0){
            for(int j=i*i;j<MX;j+=2*i){
                p[j]=1;
            }
        }
    }
    for(int i=2;i<MX;i++){
        if(p[i]==0){
            prime.push_back(i);
        }
    }
}

int main(){
    getPrime();
    while(cin>>n){
        if(n==0) break;
        for(int i=1,v=n;i<=n;i++,v--){
            cnt[i]=v;
        }
        for(int i=0;i<prime.size();i++){
            for(int j=prime[i]*2;j<=n;j+=prime[i]){
                int t=j;
                int div=0;
                while(t%prime[i]==0){                        
                    div++;
                    t/=prime[i];
                }
                cnt[prime[i]]+=cnt[j]*div;
            }
        }
        LL ans=1;
        for(int i=0;i<prime.size();i++){
            ans=(ans*(++cnt[prime[i]]))%M;
            cnt[prime[i]]=0;
        }
        printf("%lld\n",ans);
    }
}
    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice problem.

      The issue with the above code is that for each new test case , you expend π(MAX)log(MAX) operation where π(MAX) denotes the prime counting function. Since the number of primes till MAX is around MAX / 10. You put around 107 operations which becomes 109 operation over all test cases and would not pass within 3 seconds. The idea is that we process the queries in offline manner and and go through all MAX elements just once.

      Code . I have put in appropriate comments for better understanding of the idea.

      → Reply