最大公約数、最小公倍数、桁和といった簡単な関数群

funcSample.cpp

int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

int digsum(int n) {
    int res = 0;
    while(n > 0) {
        res += n % 10;
        n /= 10;
    }
    return res;
}

int phi(unsigned int n){
    if(n == 1) return 1;
    int r = n;
    for(int i = 2; i <= n; i++){
        if(!(n % i)){
            r = r * (i - 1) / i;
            while (!(n % i)){
                n /= i;
            }
        }
    }
    return r;
}