Explicație:
Daca (a,b) si (b, a) sunt perechi identice:
[tex]\displaystyle\textrm{numarul de perechi} = \sum_{b=1}^n\phi(b) [/tex]
#include <iostream>
using namespace std;
int indEuler(int x){
int ind = 1, d;
for(d = 2; x != 1; d++){
if(x%d==0){
ind *= (d-1);
x /= d;
while(x%d==0) ind *= d, x /= d;
}
d += (d%2);
}
return ind;
}
int main(){
int n, total = 0;
cin >> n;
for(int b = 1; b <= n; b++){
total += indEuler(b);
}
cout << total;
}
Daca (a,b) si (b,a) sunt perechi diferite, trebuie doar sa dublam rezultatul si sa scadem 1( de la perechea (1,1) ):
#include <iostream>
using namespace std;
int indEuler(int x){
int ind = 1, d;
for(d = 2; x != 1; d++){
if(x%d==0){
ind *= (d-1);
x /= d;
while(x%d==0) ind *= d, x /= d;
}
d += (d%2);
}
return ind;
}
int main(){
int n, total = 0;
cin >> n;
for(int b = 1; b <= n; b++){
total += indEuler(b);
}
total = total * 2 - 1;
cout << total;
}
