Cod sursa(job #3372894)

Utilizator arnold23Arnold Tempfli arnold23 Data 5 noiembrie 2026 12:55:42
Problema Pascal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.13 kb
#include <cstdio>

// How many C(n, k) are not divisible by prime p.
// Lucas: one free digit 0..d for each base-p digit d of n.
int not_div(int n, int p) {
    int prod = 1;
    if (n == 0) return 1;
    while (n > 0) {
        prod *= (n % p) + 1;
        n /= p;
    }
    return prod;
}

// How many C(n, k) have 2-adic valuation >= need (need is 1 or 2).
// Kummer: the valuation is the number of carries when adding k and n-k in base 2.
int div_by_pow2(int n, int need) {
    int ways[2][3] = {};
    ways[0][0] = 1;

    while (n > 0) {
        int bit = n & 1;
        n >>= 1;
        int nxt[2][3] = {};
        for (int cin = 0; cin <= 1; cin++) {
            for (int got = 0; got <= need; got++) {
                int w = ways[cin][got];
                if (w == 0) continue;
                for (int a = 0; a <= 1; a++) {
                    for (int b = 0; b <= 1; b++) {
                        int sum = a + b + cin;
                        if ((sum & 1) != bit) continue;
                        int cout = sum >> 1;
                        int ngot = got + cout;
                        if (ngot > need) ngot = need;
                        nxt[cout][ngot] += w;
                    }
                }
            }
        }
        for (int c = 0; c <= 1; c++) {
            for (int got = 0; got <= need; got++) ways[c][got] = nxt[c][got];
        }
    }
    return ways[0][need];
}

int digits[16];

// k is a submask of n, and every base-3 digit of k is <= that of n.
int count_submasks(int n) {
    int len = 0;
    int x = n;
    while (x > 0) {
        digits[len++] = x % 3;
        x /= 3;
    }
    if (len == 0) return 1;

    int ans = 0;
    int k = n;
    while (true) {
        int v = k;
        bool ok = true;
        for (int i = 0; i < len; i++) {
            if (v % 3 > digits[i]) {
                ok = false;
                break;
            }
            v /= 3;
        }
        if (ok && v == 0) ans++;
        if (k == 0) break;
        k = (k - 1) & n;
    }
    return ans;
}

int count_base3(int pos, int len, int val, int pow3, int n) {
    if (pos == len) return (val & n) == val;
    int ans = 0;
    for (int d = 0; d <= digits[pos]; d++) {
        ans += count_base3(pos + 1, len, val + d * pow3, pow3 * 3, n);
    }
    return ans;
}

// C(n, k) not divisible by 2 and not divisible by 3.
int neither2nor3(int n) {
    int odd = not_div(n, 2);
    int not3 = not_div(n, 3);
    if (odd <= not3) return count_submasks(n);

    int len = 0;
    int x = n;
    while (x > 0) {
        digits[len++] = x % 3;
        x /= 3;
    }
    if (len == 0) return 1;
    return count_base3(0, len, 0, 1, n);
}

int main() {
    freopen("pascal.in", "r", stdin);
    freopen("pascal.out", "w", stdout);

    int r, d;
    scanf("%d %d", &r, &d);

    int ans = 0;
    if (d == 2 || d == 3 || d == 5) {
        ans = (r + 1) - not_div(r, d);
    } else if (d == 4) {
        ans = div_by_pow2(r, 2);
    } else {
        // divisible by 6 = divisible by 2 and by 3
        int total = r + 1;
        int not2 = not_div(r, 2);
        int not3 = not_div(r, 3);
        ans = total - not2 - not3 + neither2nor3(r);
    }

    printf("%d\n", ans);
    return 0;
}