歐拉函式
- 定義
對于正整數n小于等于n的數中與n互質的數的個數記為\(\varphi(n)\),即為歐拉函式 - 歐拉公式
由算數基本定理任意一個正整數都可以寫作n=\(p_1^{a_1}p_2^{a_2}\cdots p_k^{a^k}\)
那么\(\varphi(n)=n\prod\limits_{i=1}^{k}({1-\frac{1}{p_i}})\) - 數學證明
首先\(\varphi(n)\)是一個積性函式
即 \(\varphi(a_1*a_2)=\varphi(a_1)*\varphi(a_2)\)這個的證明這里不作敘述可看這個鏈接積性證明
然后從1到一個數\(p_n^{a_n}\)一共有\(p_n^{a_n}\)個數其中與其不互質的有\(p_n,2p_n,3p_n\dots p_n^{a_n}(p_n^{a_{n-1}}*p_n)\)一共有\(p_n^{a_{n-1}}\)個數，所以與其互質的一共有\(p_n^{a_n}(1-\frac{1}{p_n})個\)
所以有：
- 代碼實作
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--)
{
int a;
scanf("%d",&a);
int res=a;
for(int i=2;i<=a/i;i++)
{
if(a%i==0)
{
res=res/i*(i-1);//注意先除再乘防止爆int
}
while(a%i==0)
{
a/=i;
}
}
if(a>1)
{
res=res/a*(a-1);
}
printf("%d\n",res);
}
return 0;
}
- 代碼細節
注意res=res/i*(i-1)這里要先除再乘防止爆int 可能會有疑問我們推導的公式中\(1-\frac{1}{p_i}\)是一個小數但是c++里/是向下取整的，那么這里會不會有問題呢?其實是完全沒問題的 我們可以看到只有當a%i==0時我們才會進行res的操作并且每次回圈中a至少都和res除i除的一樣多也就是說只要a中有約數 i 那么res中也一定有 i 一定不會出現小數，
Written with StackEdit中文版.
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/556230.html
標籤：其他
下一篇：返回列表