上午

关键词：欧拉函数。

欧拉函数

定义

对于正整数$n$，欧拉函数是指不大于$n$的数中与$n$互质的正整数的数目。例如$\phi (8)=4$，因为$1,3,5,7$均和$8$互质。

公式

$$\phi (a)=a \times \prod_{i=1}^n 1-\cfrac{1}{p_1} (a \in N_+)$$

特别的，$\phi (1)=1$。

其中$p_1,p_2,\cdots,p_n$为$a$的所有质因数，每种质因数有且只有一个。如$12=2^2*3$那么$\phi(12)=12 \times (1-\cfrac12) \times (1-\cfrac13)=4$

性质

• $\phi (n)=p^k-p^{k-1}$
• $\phi (mn)=\phi (m) \times \phi (n)$，欧拉函数是积性函数。

代码

int oula( int n ) {
    for ( int i = 1; i <= n; i++ ) {
        phi[i] = i;
    }
    for ( int i = 2; i <= n; i++ ) {
        if ( phi[i] == i ) {
            for ( int j = i; j <= n; j++ ) {
                phi[j] = phi[j] / i * ( i - 1 );
            }
        };
    }
    return phi[n];
}
int oula2( int n ) {
    vis.set();
    phi[1] = 1;
    for ( int i = 2; i <= n; i++ ) {
        if ( vis[i] ) {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for ( int j = 1; j <= cnt && prime[j] * i <= n; j++ ) {
            vis.reset( i * prime[j] );
            if ( !( i % prime[j] ) ) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            else {
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
            }
        }
    }
    return phi[n];
}
int oula3( int n ) {
    int ans = n, i;
    for ( i = 2; i * i <= n; i++ ) {
        if ( !( n % i ) )
            ans = ans / i * ( i - 1 );
        while ( !( n % i ) )
            n /= i;
    }
    if ( n > 1 ) {
        ans = ans / n * ( n - 1 );
    }
    return ans;
}

以上是三种不同的求法。

变化

与$n$互质的所有数的和

$$sum=n \times \phi (n) \div 2$$

晚上

评论区有一些问题。

版权声明：本文是原创文章，版权归 星雾月雨 所有。

本文链接：https://www.ariels.xyz/archives/334.html

本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。