欧拉函数浅析

发表于
字数统计: 1,592 | 阅读时长 ≈ 6

前言

是时候学习欧拉函数了…
手动滑稽…

侵删

欧拉函数

欧拉函数的概念

我们先来看一下欧拉函数的概念

在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。此函数以其首名研究者欧拉命名(Euler’s totient function)，它又称为Euler’s totient function、φ 函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。

好的以上引用均采取百度百科（广告时间…

实际上欧拉函数 φ （n） 求的是小于 n 的与 n 互质的数的个数

欧拉函数的通式与性质

我觉得上面那个内容很划水我们来看看能用的东西

  • 通式

(mmp Makedown的数学符号怎么打？！！！急在线等

其中 P1，P2，P3…为 x 的所有质因数，x 为不为0的正整数
φ（1）=1，
另外每种质因数只算一次…譬如12=2·2·3，我们在进行计算的时候只能每个质数用一次（不信你自己去算 φ（12）=4
若n是质数p的k次幂，，因为除了p的倍数外，其他数都跟n互质。
欧拉函数为积性函数…若m,n互质，

我们再来介绍一下一些特殊性质

  • 若 n 为奇数时，
  • 若 n 为质数时，

不打算给证明我也不会

如题，我不打算给证明，而且上述性质抄的比较多（你叫我自己写？！
博客还是主要是给自己看看的…
我给个超链接怎么样，我还是嫖百度百科的好了（已注明出处…再次声明侵删

设A, B, C是跟m, n, mn互质的数的集，据中国剩余定理，A*B和C可建立一一对应的关系。因此φ(n)的值使用算术基本定理便知，

若

则

例如

与欧拉定理、费马小定理的关系
对任何两个互质的正整数a, m(m>=2)有

即欧拉定理
当m是质数p时，此式则为：
费马小定理…
实际上，考试的时候你怎么可能自己还要去证明这个通式…能拉过来用就行了啊管他那么多你要是证完时间肯定不够啊笨
而且我拉网上资料还那么辛苦…
现在我们来看一下题目…

题目

题目描述

作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在，C君希望你告诉他队伍整齐时能看到的学生人数。

输入输出格式

输入格式：

共一个数N

输出格式：

共一个数，即C君应看到的学生人数。

输入输出样例

输入样例#1：
4
输出样例#1：
9

说明

【数据规模和约定】

对于 100% 的数据，1 ≤ N ≤ 40000

解题思路

  • 其实我们可以发现，上面讲的性质很多都是没有多大用处的…
  • 观察可知，如果我们的视线被一个人挡住了，那么在这一条线上(光沿直线传播…）看不到的人斜率是和我们看到那个人的是一样的
  • 换句话说，我们设看到第一个人的坐标为 （X1，Y1），那么之后的每个人的坐标一定是（X1·k , Y1·k)（k 为正整数）
  • 因此，我们在一条光线上看到的第一个人的 x 轴的坐标与 y 轴的坐标一定是互质的（这时以上的 k 的值为1），而之后的人的坐标 x 与 y 是有别的公因数（除去1）的
  • 另外，我们把图用直线 y=x 分割，可以发现我们分成的两部分是对称的，只需要求出其中一个部分的值 sum ，把 sum 乘2再加上直线 y = x 上我们还能看到的那个点 （1,1），答案就是 2*sum + 1
  • 而对于每一个部分，要么 x < y,要么 y < x ，因此我们就可以用欧拉函数了…我们要求的就是小于 x 的所有正整数与 x 互质的个数
  • 我们还要加个特判因为当 n = 1 的时候情况不一样…

筛选打欧拉函数表0ms

我们先预处理每个数的欧拉函数，求值的时候直接加上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))

using namespace std;

int n,ans=0;
int euler[40010];

inline void Init(){
    euler[1]=1;
    for(int i=2;i<n;i++)
        euler[i]=i;
    for(int i=2;i<n;i++)
        if(euler[i]==i)
            for(int j=i;j<n;j+=i) 
                euler[j]=euler[j]/i*(i-1);//先进行除法防止溢出下同
    return;
}

int main(){
    scanf("%d",&n);
    if(n==1){
        puts("0");
        return 0;
    }
    Init();
    rep(i,1,n-1){
        ans+=euler[i];
    }
    printf("%d",2*ans+1);
    return 0;
}

直接求每个数的欧拉函数32ms

我觉得这个复杂度也是可以让人接受的…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))

using namespace std;

int n,ans=0;;

inline int euler(int n){
    int res=n,a=n;  
    for(int i=2;i*i<=a;i++){
        if(a%i==0){
            res=res/i*(i-1);
            while(a%i==0) a/=i;
        }  
    }  
    if(a>1) res=res/a*(a-1);
    return res;  
}

int main(){
    scanf("%d",&n);
    if(n==1){
        puts("0");
        return 0;
    }
    rep(i,1,n-1){
        ans+=euler(i);
    }
    printf("%d",2*ans+1);
    return 0;
}

后记

我觉得洛谷上这道题的难度评得有点高了，一道纯裸的欧拉函数，代码也短…
我觉得OI中数论的知识还是比较重要的…多学点总是好的…
欢迎指正联系方式如下

qq： 953559040

微博： IncinblePan

洛谷： SherlockPan