精华内容
参与话题
问答
  • 欧拉函数

    2020-12-04 20:14:13
    φ(n):表示1~n中与n互质的数的个数 ...欧拉函数 #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; while (n--) { int a; cin >> a; int re

    φ(n):表示1~n中与n互质的数的个数
    在这里插入图片描述
    证明的过程是基于容斥原理进行的

    第一步:去掉1~n中所有p1、p2…pk的倍数
    第二步:加上所有第一步去重了的倍数

    欧拉函数

    #include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n;
        cin >> n;
        while (n--)
        {
            int a;
            cin >> a;
            int res = a;
            for (int i = 2; i <= a / i; i++)
            {
                if (a % i == 0)
                {
                    res = res / i * (i - 1); //注意这里要对公式进行一定的化简,保证公式中没有分数
                    while (a % i == 0)
                        a = a / i;
                }
            }
            if (a > 1)
                res = res / a * (a - 1);
            cout << res << endl;
        }
        return 0;
    }
    

    当 i mod pj == 0时,有φ(pj * i)=pj * φ(i)
    当 i mod pj != 0时,有φ(pj * i)=φ(i) * (pj-1)

    展开全文

空空如也

1 2 3 4 5 ... 20
收藏数 10,266
精华内容 4,106
关键字:

欧拉函数