Mr.Struggler's blog

By Mr.Struggler, history, 3 months 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  

»
3 months 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.

  • »
    »
    3 months 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);
        }
    }
    
    • »
      »
      »
      3 months 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.