# HackerEarth Odd divisors problem solution

In this HackerEarth Odd divisors problem solution you are given a positive integer N.f(N) is the greatest odd divisor of N. Find the sum (f(1) + f(2) + ... + f(N))%M.

## HackerEarth Odd divisors problem solution.

`#include<bits/stdc++.h>using namespace std;int T;long long N, M;long long sqr(long long x){x %= M;return x * x % M;}int main(){    cin >> T;    while(T-->0){        cin >> N >> M;        long long ans = 0;        while(N){            ans = (ans + sqr(N / 2 + N % 2)) % M;            N /= 2;        }        cout << ans << '\n';    }    return 0;}`

### second solution

`#include <bits/stdc++.h>using namespace std;typedef long long ll; const int maxn = 2e5 + 14;template<class cmp> struct LS{    vector<int> v;    vector<pair<int, int> > his;    void add(int x){    int p = lower_bound(v.begin(), v.end(), x, cmp()) - v.begin();    if(p == v.size()){        his.push_back({-1, 0});        v.push_back(x);    }    else{        his.push_back({p, v[p]});        v[p] = x;    }    }    void swap(LS<cmp> &od){  od.v.swap(v);  }    void merge(LS<cmp> &od){    if(od.v.size() > v.size())        v.swap(od.v);    for(int i = 0; i < od.v.size(); i++)        if(cmp()(od.v[i], v[i]))  v[i] = od.v[i];    }    void undo(){    assert(his.size());    if(his.back().first == -1)        v.pop_back();    else        v[his.back().first] = his.back().second;    his.pop_back();    }};typedef LS<less<int> > Lis;int p[maxn];int main(){    ios::sync_with_stdio(0), cin.tie(0);    int n;    cin >> n;    for(int i = 0; i < n; i++){        cin >> p[i];    }    Lis ans;    for(int i = 0; i < n; i++)        ans.add(p[n - i - 1]);    cout << ans.v.size() << '\n';}`