For odd numbers greatest divisor is the number itself, for even numbers keep dividing by 2 till possible.

I have done the same thing but it is giving giving time limit exceed . And when I am trying to store the result in a vector its giving memory limit exceed .

Can you provide AC solution and algorithm becuase there may be Time Limit exceed or Memory Limit Exceed issue while solving this problem

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
//write your code here
int t; cin >> t;
while(t--){
ll n; cin >> n;
ll x = (n+1)/2;
ll ans = 0;
ans += x*x;
ll ok = 0;
ll k = 2;
while(k <= n){
ok = n/k;
ok = (ok+1)/2;
ans += ok*ok ;
k = k*2;
}
cout << ans << endl;
}
return 0;
}
```

→ All odd values will be added to the answer

→ For even values take all values which have 2*odd no, 4*odd no, 8*odd no, 16*odd no… separately

i.e 2,6,10,14,18,22,26, … → sum of 1,3,5,7…

4,12,20,28,36,44… → sum of 1,3,5,7…

8,24,40,56,72… → sum of 1,3,5,7…

16,48,80 … → sum of 1,3,5,…

Sir, I was unable to understand about how to find the greatest common divisor of the even numbers .

Please explain again .

there is no need for gcd

Suppose if n=10

then we know that :-

Total Even Number=5 and Total Odd Numbers =5

Greatest odd divisor for odd no will be that no itself so totalsum for that part

will be (TotalOddNumber*TotalOddNumber)

But how to find total sum of all the greatest odd divisor for the even numbers ?

2,6,10 → 1,3,5

4 → 1

8 → 1

→ For even values take all values which have 2*odd no, 4* odd no, 8*odd no, 16* odd no… separately

i.e 2,6,10,14,18,22,26, … → 1,3,5,7…

4,12,20,28,36,44… → 1,3,5,7…

8,24,40,56,72… → 1,3,5,7…

16,48,80 … → 1,3,5,…

now u should be able to find the pattern

Thanks