Introdução
A função totiente de Euler, denotada por φ(n), conta quantos inteiros positivos menores ou iguais a n são coprimos com n Em outras palavras, φ(n) representa a quantidade de números no intervalo [1, n] que não possuem divisores comuns além de 1 com n.
Propriedades Fundamentais
1. Função Multiplicativa
A função φ(n) é uma função multiplicativa. Isso significa que se a e b são inteiros positivos coprimos (mdc(a, b) = 1), então φ(ab) = φ(a) × φ(b).
2. Valor Base
Para n = 1, temos φ(1) = 1. Este resultado é direto, pois o único inteiro positivo menor ou igual a 1 é o próprio 1, e mdc(1, 1) = 1.
3. Números Primos
Se p é um número primo, então todos os inteiros de 1 a p-1 são coprimos com p. Portanto, φ(p) = p - 1.
4. Potências de Primos
Para uma potência de primo pk (onde p é primo e k ≥ 1), temos:
φ(pk) = pk-1 × (p - 1)
Demonstração:
Vamos usar indução matemática. Para k = 1, temos φ(p) = p - 1, que é verdadeiro. Suponha que a fórmula vale para pk-1. Agora, considere os números de 1 a pk. Podemos expressar cada número como x × p^(k-1) + d, onde 0 ≤ x < p e 1 ≤ d ≤ p^(k-1).
Para que um número seja coprimo com pk, sua componente d não deve conter o fator primo p. Portanto, cada número que contribui para φ(p^(k-1)) contribui exatamente p vezes para φ(pk). Assim:
φ(pk) = φ(p^(k-1)) × p = p^(k-2) × (p - 1) × p = p^(k-1) × (p - 1)
Fórmula Geral de Cálculo
Seja n = ∏ pi^ti uma decomposição em fatores primos, onde pi são primos disitntos e ti são inteiros positivos. Então:
φ(n) = n × ∏ (pi - 1) / pi
Esta fórmula segue imediatamente das propriedades de funções multiplicativas combinadas com a propriedade para potências de primos.
Inversão Usando a Função Totiente
Relação Importante
Uma propriedade fundamental da função totiente é:
n = Σ φ(d), para todo d que divide n
Esta relação é extremamente útil em problemas de teoria dos números, especialmente em técnicas de inversão.
Aplicação em Inversão de Möbius
Na inversão de Möbius, frequentemente precisamos calcular:
Σ Σ [mdc(x, y) = 1], para 1 ≤ x, y ≤ n
Usando a função totiente, podemos simplificar esta expressão para:
2 × (Σ φ(i)) - 1
Problemas Illustrativos
Problema 1: Soma de Totientes por GCD
Dados T casos de teste, cada um com n, calcular:
Σ Σ φ(gcd(x, y)), para 1 ≤ x, y ≤ n
(T ≤ 5000, n ≤ 10^7)
Solução:
Vamos derivar a fórmula de solução:
Σ Σ φ(gcd(x, y)) = Σ φ(d) × Σ Σ [gcd(x, y) = 1]
Onde as somas internas variam de 1 a ⌊n/d⌋.
Simplificando, obtemos:
Σ φ(d) × (2 × Σ φ(i) - 1)
A implementação usa crivo linear para calcular φ(i) para todos os i até 10^7 e pré-calcular a soma prefixada.
#include<bits/stdc++.h>
using namespace std;
using int64 = long long;
const int MAXN = 10000010;
int np[MAXN];
int prime[MAXN];
int64 phi[MAXN];
int64 prefix[MAXN];
int primeCount = 0;
void precompute() {
memset(np, true, sizeof(np));
np[0] = np[1] = false;
phi[1] = prefix[1] = 1;
for (int i = 2; i < MAXN; i++) {
if (np[i]) {
prime[++primeCount] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= primeCount && prime[j] * i < MAXN; j++) {
int val = prime[j] * i;
np[val] = false;
if (i % prime[j] == 0) {
phi[val] = phi[i] * prime[j];
break;
} else {
phi[val] = phi[i] * phi[prime[j]];
}
}
prefix[i] = prefix[i-1] + phi[i];
}
}
int64 solve(int n) {
int64 ans = 0;
int pos = 1, D, right;
while (pos <= n) {
D = n / pos;
right = n / D;
int64 sumPhi = prefix[right] - prefix[pos-1];
int64 total = (prefix[D] * 2 - 1);
ans += sumPhi * total;
pos = right + 1;
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
precompute();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
cout << solve(n) << "\n";
}
return 0;
}
Problema 2: Contagem de Pontos Colineares
Em uma grade de n × m pontos, contar o número de formas de escolher três pontos que estejam em linha reta. A ordem dos pontos não importa.
(n, m ≤ 10^5)
Solução:
Primeiro, calculamos as linhas horizontais e verticais:
ans1 = n × C(m, 3) + m × C(n, 3)
Para linhas inclinadas, seja (x, y) a diferença entre as coordenadas x e y das extremidades. O número de pontos intermediários é gcd(x, y) - 1.
ans2 = 2 × Σ Σ (gcd(i, j) - 1) × (n - i) × (m - j)
Usando a identidade n = Σ φ(d), transformamos o problema em:
t1 = Σ φ(d) × Σ (n - i × d) × Σ (m - j × d)
#include<bits/stdc++.h>
using namespace std;
using int64 = long long;
const int64 MOD = 1000000007LL;
int64 n, m;
int limit;
int prime[100000];
int64 totient[100000];
bool isComp[100000];
int totalPrime = 0;
void prepare() {
memset(isComp, true, sizeof(isComp));
isComp[0] = isComp[1] = false;
totient[1] = 1;
limit = min(n, m);
for (int64 i = 2; i <= max(n, m); i++) {
if (isComp[i]) {
prime[++totalPrime] = i;
totient[i] = i - 1;
}
for (int j = 1; j <= totalPrime && prime[j] * i < limit; j++) {
int64 val = prime[j] * i;
isComp[val] = false;
if (i % prime[j] == 0) {
totient[val] = totient[i] * prime[j];
break;
} else {
totient[val] = totient[i] * totient[prime[j]];
}
}
}
}
int64 arithmeticSeries(int64 first, int64 last, int64 count) {
return ((first + last) * count / 2) % MOD;
}
int64 calculate() {
int64 result = 0;
for (int64 d = 1; d < limit; d++) {
int64 nDiv = (n - 1) / d;
int64 mDiv = (m - 1) / d;
int64 t1 = arithmeticSeries(n - d, n - nDiv * d, nDiv);
int64 m1 = arithmeticSeries(m - d, m - mDiv * d, mDiv);
result = (result + t1 * m1 % MOD * totient[d]) % MOD;
}
return (result * 2) % MOD;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
prepare();
int64 answer = calculate();
int64 vertical = ((n - 1) * n / 2) % MOD * ((m - 1) * m / 2) % MOD;
answer = (answer - 2 * vertical % MOD + MOD) % MOD;
if (n >= 3) {
answer = (answer + m * (n * (n - 1) * (n - 2) / 6) % MOD) % MOD;
}
if (m >= 3) {
answer = (answer + n * (m * (m - 1) * (m - 2) / 6) % MOD) % MOD;
}
cout << answer % MOD << "\n";
return 0;
}
Aplicações em Aritmética Modular
Teorema de Euler
Para inteiros a e m coprimos, temos:
a^φ(m) ≡ 1 (mod m)
Este teorema é a base para o cálculo de potências modulares e possui aplicações importantes em criptografia.
Redução Exponencial
Para calcular 2^n (mod m) onde n pode ser muito grande, podemos usar a propriedade de que aplicar repetidamente a função totiente eventualmente reduz o expoente a um valor gerenciável.
Para inteiros maiores que 1:
- Se n é ímpar, contém um fator primo ímpar, então φ(n) é par.
- Se n é par, contém o fator primo 2, então φ(n) ≤ n/2.
Portanto,只需要 O(log n) aplicações da função totiente para reaches 1.
#include<bits/stdc++.h>
using namespace std;
using int64 = long long;
const int MAXN = 500200;
const int MAXP = 10000;
int64 primeList[MAXP];
int64 phiValues[MAXN];
bool isPrime[MAXN];
int primeCnt = 0;
void sieveInit() {
memset(isPrime, true, sizeof(isPrime));
isPrime[0] = isPrime[1] = false;
phiValues[1] = 1;
for (int i = 2; i < MAXN; i++) {
if (isPrime[i]) {
primeList[++primeCnt] = i;
phiValues[i] = i - 1;
}
for (int j = 1; j <= primeCnt && primeList[j] * i < MAXN; j++) {
int64 val = primeList[j] * i;
isPrime[val] = false;
if (i % primeList[j] == 0) {
phiValues[val] = phiValues[i] * primeList[j];
break;
} else {
phiValues[val] = phiValues[i] * phiValues[primeList[j]];
}
}
}
}
int64 getPhi(int64 x) {
int64 result = x;
int64 temp = x;
if (x < MAXN) {
return phiValues[x];
}
for (int i = 1; i <= primeCnt && primeList[i] * primeList[i] <= temp; i++) {
if (temp % primeList[i] == 0) {
result = result / primeList[i] * (primeList[i] - 1);
while (temp % primeList[i] == 0) {
temp /= primeList[i];
}
}
}
if (temp > 1) {
result = result / temp * (temp - 1);
}
return result;
}
int64 modPow(int64 base, int64 exp, int64 mod) {
int64 result = 1;
base %= mod;
while (exp) {
if (exp & 1) result = result * base % mod;
exp >>= 1;
base = base * base % mod;
}
return result;
}
int64 solveCase(int64 mod) {
int64 phiChain[100];
int depth = 0;
phiChain[0] = mod;
while (phiChain[depth] > 1) {
phiChain[depth + 1] = getPhi(phiChain[depth]);
depth++;
}
phiChain[++depth] = 1;
int64 result = 2;
for (int i = depth; i > 0; i--) {
result %= phiChain[i];
result += phiChain[i];
result = modPow(2, result, phiChain[i-1]);
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
sieveInit();
int T;
cin >> T;
while (T--) {
int64 mod;
cin >> mod;
cout << solveCase(mod) << "\n";
}
return 0;
}
Conclusão
A função totiente de Euler é uma ferramenta fundamental em teoria dos números, com aplicações que vão desde problemas de contagem até criptografia moderna. As propriedades multiplicativas e a relação de inversão com a função identidade tornam-na indispensável no estudo de algoritmos de teoria dos números, especialmente em programação competitiva.