数论 - 欧拉函数【普通求法 + 筛法求欧拉函数】

向右看齐 2021-07-24 23:53 471阅读 0赞

## **欧拉函数** ##

### **1.定义** ###

对于正整数n,欧拉函数是小于或等于n的正整数中(即1-n中)与n互质的数的数目，记作φ(n)  
其中φ(1)=1。

### **2求n的欧拉值** ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

### 3.结论 ###

![!\[在这里插入图片描述\](https://img-blog.csdnimg.cn/20200724120852476.png][https_img-blog.csdnimg.cn_20200724120852476.png]

### **4.代码模板：** ###

int phi(int x)
    { 
        int res = x;
        for (int i = 2; i <= x / i; i ++ )
            if (x % i == 0)
            { 
                res = res / i * (i - 1);
                while (x % i == 0) x /= i;
            }
        if (x > 1) res = res / x * (x - 1);
    
        return res;
    }

### **5.筛法求欧拉函数** ###

int primes[N], cnt;     // primes[]存储所有素数
    int euler[N];           // 存储每个数的欧拉函数
    bool st[N];         // st[x]存储x是否被筛掉
    
    
    void get_eulers(int n)
    { 
        euler[1] = 1;
        for (int i = 2; i <= n; i ++ )
        { 
            if (!st[i])
            { 
                primes[cnt ++ ] = i;
                euler[i] = i - 1;
            }
            for (int j = 0; primes[j] <= n / i; j ++ )
            { 
                int t = primes[j] * i;
                st[t] = true;
                if (i % primes[j] == 0)
                { 
                    euler[t] = euler[i] * primes[j];
                    break;
                }
                euler[t] = euler[i] * (primes[j] - 1);
            }
        }
    }

质数i的欧拉函数即为euler\[i\] = i - 1 因为1到i−1均与i互质，共i−1个。  
euler\[primes\[j\] \* i\]分为两种情况：  
① i % primes\[j\] == 0时：primes\[j\]是i的最小质因子，也是primes\[j\] \* i的最小质因子，因此1 - 1 / primes\[j\]这一项在euler\[i\]中计算过了，只需将基数N修正为primes\[j\]倍，最终结果为euler\[i\] \* primes\[j\]。  
② i % primes\[j\] != 0：primes\[j\]不是i的质因子，只是primes\[j\] \* i的最小质因子，因此不仅需要将基数N修正为primes\[j\]倍，还需要补上1 - 1 / primes\[j\]这一项，因此最终结果euler\[i\] \* (primes\[j\] - 1)。

### 6.题目练习 ###

##### (1)AcWing -873. 欧拉函数 #####

给定n个正整数ai，请你求出每个数的欧拉函数。  
**欧拉函数的定义**  
![在这里插入图片描述][202007291002108.png]

**输入格式**  
第一行包含整数n。  
接下来n行，每行包含一个正整数ai。  
**输出格式**  
输出共n行，每行输出一个正整数ai的欧拉函数。  
**数据范围**  
1≤n≤100,  
1≤ai≤2∗109  
**输入样例：**  
3  
3  
6  
8  
**输出样例：**  
2  
2  
4  
**代码**

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int main()
    { 
    	int n;
    	cin >> n;
    	while (n--)
    	{ 
    		int a;
    		cin >> a;
    		int ans = a;
    		for (int i = 2; i <= a / i; i++)
    		{ 
    			if (a%i == 0)
    			{ 
    				ans = ans / i * (i - 1); //避免越界
    				while (a%i == 0)
    				{ 
    					a /= i;
    				}
    			}
    		}
    		if (a > 1) ans = ans / a * (a - 1);
    		cout << ans << endl;
    	}
    	return 0;
    }

##### (2)AcWing- 874. 筛法求欧拉函数 #####

给定一个正整数n，求1~n中每个数的欧拉函数之和。  
**输入格式**  
共一行，包含一个整数n。  
**输出格式**  
共一行，包含一个整数，表示1~n中每个数的欧拉函数之和。  
**数据范围**  
1≤n≤106  
**输入样例：**  
6  
**输出样例：**  
12  
**代码**

#include<iostream>
    #include<cstdio>
    typedef long long ll;
    using namespace std;
    const int N = 1e6 + 10;
    int primes[N], cnt;
    int euler[N];
    bool st[N];
    void get_eulers(int n)
    { 
    	euler[1] = 1;
    	for (int i = 2; i <= n; i++)
    	{ 
    		if (!st[i])
    		{ 
    			primes[cnt++] = i;
    			euler[i] = i - 1;
    		}
    		for (int j = 0; primes[j] <= n / i; j++)
    		{ 
    			st[i*primes[j]] = 1;
    			if (i%primes[j] == 0)
    			{ 
    				euler[i*primes[j]] = euler[i] * primes[j];
    				break;
    			}
    			euler[i*primes[j]] = euler[i] * (primes[j] - 1);
    		}
    	}
    }
    int main()
    { 
    	int n;
    	cin >> n;
    	get_eulers(n);
    	ll ans = 0;
    	for (int i = 1; i <= n; i++)
    	{ 
    		ans += euler[i];
    	}
    	cout << ans << endl;
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/6e843440576b4a779cecbaf0c1b3d3bb.png
[https_img-blog.csdnimg.cn_20200724120852476.png]: /images/20210724/8572e6df1f6f4e479e57332b3e7fa83b.png
[202007291002108.png]: /images/20210724/58d66b3e17764d85815360217ae34d71.png