Énoncé du problème

Soit une fonction f définie pour tout entier positif n vérifiant :

∑d|n f(d) = n

Étant donnés n entiers a1, a2, …, an, calculer ∑i=1n f(ai).

Méthode de résolution

La fonction f n'est autre que l'indicatrice d'Euler φ. Elle possède les propriétés suivantes :

• Si q = nm avec n et m premiers entre eux, alors f(q) = f(n) × f(m).
• Si q est premier, f(q) = q − 1.
• Si q = n × m, m divise q et m2 divise q, alors f(q) = f(n) × m.
• Si q = pk avec p premier, alors f(q) = pk−1 × (p − 1).

On peut donc calculer f pour tous les entiers jusqu'à une borne maximale à l'aide d'un crible linéaire en O(N).

Une autre approche consiste à factoriser chaque entier individuellement en ses facteurs premiers, puis à appliquer la formule φ(x) = x × ∏p|x (1 − 1/p), ou la forme équivalente déduite des puissances premières : si x = ∏ piei, alors φ(x) = ∏ piei−1 × (pi − 1). Chaque terme peut être calculé via une exponentiation rapide.

Implémnetation avec crible linéaire

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int MAXV = 10000001;
int phi[MAXV];
bool isComp[MAXV];
vector<int> primes;

void compute_phi(int limit) {
    phi[1] = 1;
    for (int i = 2; i <= limit; ++i) {
        if (!isComp[i]) {
            primes.push_back(i);
            phi[i] = i - 1;
        }
        for (int p : primes) {
            ll v = 1LL * i * p;
            if (v > limit) break;
            isComp[v] = true;
            if (i % p == 0) {
                phi[v] = phi[i] * p;
                break;
            }
            phi[v] = phi[i] * (p - 1);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    compute_phi(MAXV - 1);
    int n;
    cin >> n;
    ll sum = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        sum += phi[x];
    }
    cout << sum << '\n';
    return 0;
}

Implémentation par factorisation individuelle

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll fast_pow(ll base, int exp) {
    ll res = 1;
    while (exp) {
        if (exp & 1) res *= base;
        base *= base;
        exp >>= 1;
    }
    return res;
}

ll phi_single(int x) {
    if (x == 1) return 1;
    ll res = 1;
    int y = x;
    for (int i = 2; i * i <= y; ++i) {
        if (y % i == 0) {
            int cnt = 0;
            while (y % i == 0) {
                ++cnt;
                y /= i;
            }
            res *= fast_pow(i, cnt - 1) * (i - 1);
        }
    }
    if (y > 1) res *= y - 1;   // y est un facteur premier
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    ll total = 0;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        total += phi_single(a);
    }
    cout << total << '\n';
    return 0;
}

Les deux méthodes donnent des résultats corrects. Le crible est plus efficace pour un grand nombre de valeurs, tandis que la factorisation endividuelle évite de stocker un tableau de grande taille.