Функція Фенвіка#1648

Функція Фенвіка (Розбір)

Значення функції Фенвіка дорівнює НСД (найбільшому спільному дільнику) аргументу й достатньо великого степеня двійки. У цій задачі достатньо взяти $2^{30}$ 2^{30}, оскільки $n < 2^{31}$ n < 2^{31}.

У 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++

У 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