
i always get tle... and i can't use 200000*200000 array...
Moderator: Board moderators
It is possible to compute the whole array! For this study what ismf wrote: Now, the sum in the problem statement is just 1*a[n/1] + 2*a[n/2] + 3*a[n/3] + ... + n*a[n/n]. This formula is enough for 11426, but I've got a TLE with it on 11424. One way to optimize is to notice that there are at most 2*sqrt(n) distinct values that quotient n/i can take, and cleverly iterate just over them.
Code: Select all
G[n]-G[n-1]=sum(i=1,n-1,gcd(i,n))
Code: Select all
Removed
You can't get AC with a O(N^2) algorithm. Read the previous posts carefully to get an idea of an efficient solution.Obaida wrote:How I could reduce time here... Some one please help me...
Your code is still slow and bad. Here it is my (first) method with more details in pseudocode:f74956227 wrote: I use a table to store the number by a[n]-a[n-1]=sum(i=1,n-1,gcd(i,n)) , but is still too slow... can someone help me plz
Code: Select all
compute eulerphi in [1,N] by sieving (it can be done in O(N*loglog(N)) time)
(type of G array is long long int)
for k=1 to k=N let G[k]=0
for k=1 to k=N
for n=2*k to n=N step k let G[n]+=k*eulerphi[n/k]
for k=2 to k=N let G[k]+=G[k-1]
and now you're ready: G[n]=sum(i=1,n,sum(j=i+1,n,gcd(i,j)) for every 1<=n<=N integer.
You need to declare them in dynamic way, otherwise you run out of judge's heap (it was 8 MB on the old judge), so to avoid RTE you need to do:f74956227 wrote: now i am trying 1 am trying 10426 but always runtime error QQ by the same algorithm with MAX = 4000100 and long long a[MAX]
Code: Select all
int *eulerphi;
long long int **G;
eulerphi=(int*) (malloc) ((MAX+1)*sizeof(int));
G=(long long int*) (malloc) ((MAX+1)*sizeof(long long int));