Cod sursa(job #2240401)

Utilizator cristina_borzaCristina Borza cristina_borza Data 13 septembrie 2018 11:02:30
Problema Light2 Scor 100
Compilator cpp Status done
Runda simulare_prega Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("light2.in");
ofstream g ("light2.out");

long long n, ans, v[50];
int k;

long long FindGcd (long long a, long long b) {
    long long r = a % b;
    while (r) {
        a = b;
        b = r;
        r = a % b;
    }

    return b;
}

void bkt (int pos, long long lcm, long long sgn, long long nr) {
    if (lcm > n) return;
    if (pos > k) {
        ans += sgn * (nr / 2) * (n / lcm);
        return;
    }

    bkt (pos + 1, lcm, sgn, nr);
    if (sgn == 1)
        bkt (pos + 1, lcm * v[pos] / FindGcd(lcm, v[pos]), -1, nr * 2);
    else
        bkt (pos + 1, lcm * v[pos] / FindGcd(lcm, v[pos]), 1, nr * 2);
}

int main() {
    f >> n >> k;
    for (int i = 1; i <= k; ++ i) {
        f >> v[i];
    }

    bkt (1, 1, 0, 1);
    g << ans << '\n';

    return 0;
}