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 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,…
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 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
Thanks 