P8255 Jeu Mathématique

Si x ne divise pas z, aucune solution n'exitse. En décomposant x = d*a et y = d*b avec gcd(a,b) = 1, on a gcd(x,y) = d. Ainsi, z = x * y * gcd(x,y) = d^3 * a * b. À partir de x et z, on calcule le quotient q = z/x = d^2 * b. Ensuite, on évalue g = gcd(q, x^2) = d^2. Si g n'est pas un carré parfait, il n'y a pas de solution. Sinon, on extrait d comme racine carrée de g, puis y = q / d.

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
int main() {
    ll X, Z;
    cin >> X >> Z;
    if (Z % X != 0) {
        cout << -1 << endl;
        return 0;
    }
    ll quotient = Z / X;
    ll common_div = __gcd(X * X, quotient);
    ll sqrt_val = sqrt(common_div);
    if (sqrt_val * sqrt_val != common_div) {
        cout << -1 << endl;
        return 0;
    }
    ll Y = quotient / sqrt_val;
    cout << Y << endl;
    return 0;
}
</algorithm></cmath></iostream>

P1082 Équation de Congruence

Ce problème est un exercice standard pour l'algorithme d'Euclide étendu (exgcd). Il s'agit de trouver un entier x tel que a*x ≡ 1 (mod b), ce qui revient à résoudre a*x + b*y = 1 pour x et y.

#include <iostream>
using namespace std;
typedef long long ll;
ll extended_gcd(ll a, ll b, ll& coeff_x, ll& coeff_y) {
    if (b == 0) {
        coeff_x = 1;
        coeff_y = 0;
        return a;
    }
    ll gcd_val = extended_gcd(b, a % b, coeff_y, coeff_x);
    coeff_y -= (a / b) * coeff_x;
    return gcd_val;
}
int main() {
    ll A, B;
    cin >> A >> B;
    ll X, Y;
    extended_gcd(A, B, X, Y);
    ll result = (X % B + B) % B;
    cout << result << endl;
    return 0;
}
</iostream>

P1390 Somme des Diviseurs Communs

On utilise une approche de crible pour calculer le nombre de paires (i,j) avec gcd(i,j) = k, noté f_k. Soit g_k = ⌊n/k⌋^2 le nombre de paires où k divise gcd(i,j). Par inclusion-exclusion, f_k = g_k - somme des f_{multiple de k}. La réponse finale est (Σ k*f_k - Σ gcd(i,i)) / 2, où Σ gcd(i,i) correspond à la somme des entiers de 1 à n.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int main() {
    ll N;
    cin >> N;
    vector<ll> pair_count(N + 1, 0);
    ll total_sum = 0;
    for (ll divisor = N; divisor >= 1; --divisor) {
        ll count = N / divisor;
        pair_count[divisor] = count * count;
        for (ll multiple = 2 * divisor; multiple <= N; multiple += divisor) {
            pair_count[divisor] -= pair_count[multiple];
        }
        total_sum += pair_count[divisor] * divisor;
    }
    ll ans = (total_sum - N * (N + 1) / 2) / 2;
    cout << ans << endl;
    return 0;
}
</ll></vector></iostream>

P1516 Date de la Grenouille

On doit résoudre l'équation x + k*m ≡ y + k*n (mod l) pour k. En réarrangeant, on obtient k*(m-n) - l*z = -(x-y) pour un entier z. Cela se ramène à une équation diophantienne résoluble via l'algorithme d'Euclide étendu, où l'on cherche k modulo l/gcd(m-n, l).

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
ll extended_gcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extended_gcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}
int main() {
    ll start_pos1, start_pos2, step1, step2, modulo;
    cin >> start_pos1 >> start_pos2 >> step1 >> step2 >> modulo;
    ll diff = start_pos2 - start_pos1;
    ll coef_step = step1 - step2;
    ll x, y;
    ll gcd_val = extended_gcd(coef_step, modulo, x, y);
    if (diff % gcd_val != 0) {
        cout << "Impossible" << endl;
    } else {
        x *= diff / gcd_val;
        ll period = abs(modulo / gcd_val);
        ll result = (x % period + period) % period;
        cout << result << endl;
    }
    return 0;
}
</cmath></iostream>

P4777 Théorème des Restes Chinois Étendu (EXCRT)

Le théorème des restes chinois étendu permet de résoudre un système d'équations de congruence lorsque les moduli ne sont pas nécessairement premiers entre eux. On applique une approche itérative en fusionnant progressivement les conrguences via l'algorithme d'Euclide étendu.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
ll extended_gcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extended_gcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}
int main() {
    int n;
    cin >> n;
    vector<ll> moduli(n), residues(n);
    for (int i = 0; i < n; ++i) {
        cin >> moduli[i] >> residues[i];
    }
    ll current_lcm = moduli[0];
    ll current_res = residues[0] % current_lcm;
    for (int i = 1; i < n; ++i) {
        ll a = current_lcm, b = moduli[i], c = residues[i] - current_res;
        ll x, y;
        ll d = extended_gcd(a, b, x, y);
        if (c % d != 0) {
            cout << -1 << endl;
            return 0;
        }
        x = (c / d) * x;
        ll new_lcm = a * (b / d);
        current_res = (current_res + x * a) % new_lcm;
        if (current_res < 0) current_res += new_lcm;
        current_lcm = new_lcm;
    }
    cout << current_res << endl;
    return 0;
}
</ll></vector></iostream>