 Please provide hint for this problem : )

1 Like

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

1 Like

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()
{
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;
}
2 Likes

→ For even values take all values which have 2odd no, 4odd no, 8odd no, 16odd 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,…

1 Like

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

there is no need for gcd

1 Like

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 2odd no, 4 odd no, 8odd 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

1 Like

Thanks 