### Mr.Struggler's blog

By Mr.Struggler, history, 5 months ago, ,

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);
}
}


•
• -3
•

 » 5 months ago, # |   +5 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.
•  » » 5 months ago, # ^ |   0 got TLE #include using namespace std; #define MX 5000005 #define M 100000007 #define LL long long #define dbg(x) cout<<#x<<" = "< prime; void getPrime(){ p[0]=p[1]=1; for(int i=4;i>n){ if(n==0) break; for(int i=1,v=n;i<=n;i++,v--){ cnt[i]=v; } for(int i=0;i
•  » » » 5 months ago, # ^ |   0 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.