オイラーのトーティエント関数

目的

与えられた自然数$n$に対してオイラーのトーティエント関数$\phi(n)$($1,...,i$のうち$i$と互に素な整数の個数)の値を返します。

使い方

long totient_function(ArrayList f,long n)
$\phi(n)$をreturn。リストfにはnを素因数分解した時の各素因数とその個数を格納しておいてください。

ソースコード

long totient_function(ArrayList<Factor> f, long n) {
    long ret = n;
    for (int i = 0; i < f.size(); i++) {
	ret = ret - ret / f.get(i).base;
    }
    return ret;
}


class Factor{
    long base, cnt;
    Factor(long base, long cnt){
	this.base = base;
	this.cnt = cnt;
    }
}

Verified

yukicoder No.385 カップ麺生活