Problème A : Dénombrement de triplets produits

Le premier exercice demande de compter les triplets d'entiers strictement positifs $(a, b, c)$ vérifiant $a \times b \times c \le K$. Une stratégie efficace consiste à itérer sur les deux premières variables et à déduire directement le nombre de valeurs admissibles pour la troisième. Pour chaque couple $(a, b)$ fixé, le plafond de $c$ est exactement $\lfloor K / (a \times b) \rfloor$. La convergence rapide des itérateurs secondaires s'appuie sur la décroissance harmonique, limitant la complexité temporelle.

#include <iostream>

int main() {
    long long lim;
    std::cin >> lim;
    long long total = 0;
    for (long long a = 1; a <= lim; ++a) {
        for (long long b = 1; b * a <= lim; ++b) {
            total += lim / (a * b);
        }
    }
    std::cout << total << '\n';
    return 0;
}

Problème B : Réduction d'exposant par indicatrice d'Euler

Cette étape vise à extraire la dernière décimale de la tour $A^{B^C}$. Lorsque le module est 10, la fonction indicatrice d'Euler vaut $\varphi(10) = 4$. Le théorème d'Euler généralisé autorise la réduction de l'exposant secondaire modulo $\varphi(10)$, en y ajoutant $\varphi(10)$ pour préserver l'égalité même lorsque l'exposant réel est inférieur au seuil de réduction. Une routine de puissance modulaire itérative finalise l'évaluation.

#include <iostream>

long long modular_pow(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

long long euler_phi(long long n) {
    long long res = n;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            res -= res / p;
        }
    }
    if (n > 1) res -= res / n;
    return res;
}

int main() {
    long long a, b, c;
    std::cin >> a >> b >> c;
    long long phi_10 = euler_phi(10);
    long long reduced_exp = modular_pow(b, c, phi_10) + phi_10;
    std::cout << modular_pow(a, reduced_exp, 10) << '\n';
    return 0;
}

Problème C : Balayage de chaînes et correction de surcomptage

L'algorithme effectue un parcours séquentiel de la chaîne pour repérer les positions initiatrices d'une transformation conditionnelle. Lorsqu'un caractère identique à son successeur est détecté, sans violation de la règle de triplet immédiat et sans chevauchement avec une opération précédente, la contribution potentielle est additionnée au compteur global. Un mécanisme de régulation décrémente le score lorsqu'une séquence se rattache à un motif déjà traité, garantissant ainsi l'intégrité du dénombrement.

#include <iostream>
#include <string>

int main() {
    std::string txt;
    std::cin >> txt;
    int len = txt.length();
    long long score = 0;
    char prev_char = '\0';

    for (int i = 0; i < len; ++i) {
        bool cond_succ = (i + 1 < len) && (txt[i] == txt[i + 1]);
        bool cond_next = (i + 2 >= len) || (txt[i] != txt[i + 2]);
        bool cond_prev = (txt[i] != prev_char);

        if (cond_succ && cond_next && cond_prev) {
            score += (len - i);
            prev_char = txt[i];
        } else if (txt[i] == prev_char) {
            score -= 1;
        }
    }
    std::cout << score << '\n';
    return 0;
}

Problème D : Combinatoire sous contrainte de domination

Le défi consiste à déterminer le nombre de paires de tableaux $A$ et $B$ de tailes $n$ et $m$, à valeurs entières dans $[1, k]$, telles que chaque élément de $B$ soit supérieur ou égal au maximum de $A$. On fixe la valeur du maximum de $A$ à $i$. Le nombre de façons de construire ce tableau avec un maximum exact est donné par la différence $i^n - (i-1)^n$. Parallèlement, chaque case de $B$ peut prendre une valeur dans $[i, k]$, offrant $(k - i + 1)^m$ configurations. L'agrégation de ces termes sur tout l'intervalle $[1, k]$, évaluée sous modulo $998244353$, fournit la solution.

#include <iostream>

const int MOD = 998244353;

long long power(long long base, int exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

int main() {
    int n, m, k;
    std::cin >> n >> m >> k;
    long long total = 0;

    for (int i = 1; i <= k; ++i) {
        long long ways_a = (power(i, n) - power(i - 1, n) + MOD) % MOD;
        long long ways_b = power(k - i + 1, m);
        total = (total + ways_a * ways_b) % MOD;
    }
    std::cout << total << '\n';
    return 0;
}