Fenwick Function#1648

Fenwick Function (Editorial)

The value of the Fenwick function can be found by calculating the GCD (greatest common divisor) of a given number and a sufficiently large power of two. In this problem, $2^{30}$ 2^{30} is enough because $n < 2^{31}$ n < 2^{31}.

In C++,

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    int k = 1073741824; // 2^30
    cout << gcd(n, k);
}

C++

In Python,

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

n = int(input())
k = 2**30
print(gcd(n, k))

Python