首页 > 其他分享 >【数学/数论】欧拉函数 - Phi

【数学/数论】欧拉函数 - Phi

时间:2024-01-16 13:55:43浏览次数:41  
标签:Phi 函数 数论 varphi mathsf underline 欧拉 gcd

引言

自 Mr.果 讲了 CF1900D 之后,决定复习 n 月之前学习的知识:欧拉函数。


\[\Large{{一、\underline{定义}}} \]

\[\scriptsize \mathsf {一切的开始} \]

欧拉函数,即 \(\varphi(x)\)。

\[\varphi(x) = \sum_{i = 1}^{x} [\gcd(x,i) = 1] \]

它表示小于等于 \(x\) 的数中,与 \(x\) 互质的数的个数。

特别的,

  1. \(\varphi(1) = 1\);

  2. \(\varphi(p) = p - 1\)(\(p\) 为质数);


\[\Large{\mathsf{二、\underline{性质}}} \]

\[\scriptsize \mathsf{解题或优化的关键} \]

  1. \(\varphi(x)\) 为积性函数。

\[\begin{cases} \varphi(xy) = \varphi(x) \times \varphi(y) & \text{ if } \gcd(x, y) = 1\\ \varphi (2x) = \varphi(x) & \text{ if } x \bmod 2 = 1 \end{cases} \]

用途: 线性筛法求范围内所有 \(\varphi(x)\)。

  1. 欧拉反演
    一个正整数 \(n\) 可以表示为:

\[ n = \sum_{d \mid n}{\varphi(d)} \]

证明

如果 \(\gcd(k, n) = d\),那么

\(\gcd(\dfrac{k}{d},\dfrac{n}{d}) = 1\), \(( k < n )\)。

如果我们设 \(f(x)\) 表示 \(\gcd(k, n) = x\) 的数的个数,那么
\(n = \sum_{i = 1}^n{f(i)}\)。

根据上面的证明,我们发现,

\(f(x) = \varphi(\dfrac{n}{x})\),从而
\(n = \sum_{d \mid n}\varphi(\dfrac{n}{d})\)。注意到约数 d 和 \( \dfrac{n}{d}\) 具有对称性,所以上式化为 \(n = \sum_{d \mid n}\varphi(d)\)。

\(\tiny (Ctrl\; + \;v \;不要 \%)\)


\[\Large{\mathsf{三、\underline{应用}}} \]

\[\scriptsize \mathsf{一些较为基础的套路 or 算法} \]

\[\large{\mathsf{1、\underline{线性筛求欧拉函数}}} \]

基本用途:对于要使用多个 \(\varphi(x)\) 的值时,如果一个一个 \(O(\sqrt n)\) 的求,效率将会很慢,而该算法适用于求一定值域范围内的所有欧拉函数值。

Time: \(\text{O}(n)\quad\) **Memory: **\(\text{O}(n)\)

使用性质:欧拉函数是积性函数。

小声BB:所有积性函数都可以用线性筛来求

ll pri[M], tot, phi[M];
bool isp[M];
// pri -> 储存素数(线性筛的基本框架)
// tot -> 素数个数
// isp -> 是否是素数
// phi -> 欧拉函数值
void pre(int Max){// Max -> 上界
    for(int i = 1; i <= Max; i ++) isp[i] = 1;
    isp[1] = 0;
    phi[1] = 1;//phi(1) = 1
    for(int i = 2; i <= Max; i ++){
        if(isp[i]){
            pri[++ tot] = i;
            phi[i] = i - 1;//除了1以外,所有小于等于质数的数都与质数互质
        }
        for(int j = 1;j <= tot && i * pri[j] <= Max;j ++){
            isp[i * pri[j]] = 0;
            if(i % pri[j]) phi[i * pri[j]] = phi[i] * phi[pri[j]];//积性函数的性质
            else{
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            }
        }
    }
}

\[\large{\mathsf{2、\underline{gcd 求和}}} \]

额,我也不会证,看看 dalao 的博客吧

Link

标签:Phi,函数,数论,varphi,mathsf,underline,欧拉,gcd
From: https://www.cnblogs.com/Ice-lift/p/17967515

相关文章

  • delphi firemonkey使用 TListView 自定义列表数据
    设计界面如下把ListView的Item的Appearance为DynamicAppearance,并且把Item改为高度100添加Item代码procedureTForm1.Button1Click(Sender:TObject);varimg:TListItemImage;text1,text2,text3:TListItemText;beginvaritem:=ListView1.Items.Add;text......
  • 数论好题 CF900D
    前置推导令\(b_1=\frac{a_1}{x},b_2=\frac{a_2}{x},\dots,b_n=\frac{a_n}{x}\)。很显然\(b_i\)为整数,且\(b\)数组的全部元素互质,即\(gcd(b_1,b_2,b_3,\dots,b_n)=1\)。因为\[\sum_{i=1}^{n}a_i=y\]所以\[x\times\sum_{i=1}^{n}b_i=y\]\[\sum_{i=......
  • 数论好题 CF900D
    前置推导令\(b_1=\frac{a_1}{x},b_2=\frac{a_2}{x},\dots,b_n=\frac{a_n}{x}\)。很显然\(b_i\)为整数,且\(b\)数组的全部元素互质,即\(gcd(b_1,b_2,b_3,\dots,b_n)=1\)。因为\[\sum_{i=1}^{n}a_i=y\]所以\[x\times\sum_{i=1}^{n}b_i=y\]\[\sum_{i=......
  • Windows 硬件信息监控工具 OhmGraphite 部署
    1、下载OhmGraphitehttps://github.com/nickbabcock/OhmGraphite/releases2、修改OhmGraphite.exe.config配置(此处使用Prometheus做为数据源)<?xmlversion="1.0"encoding="utf-8"?><configuration><appSettings><addkey="t......
  • dolphinscheduler 3.2.0版本执行install.sh脚本报错 command not found
    环境:linuxcentos7dolphinscheduler集群安装,正确配置完/env/install_env.sh、/env/dolphinscheduler_env.sh脚本后,执行安装脚本报错。排错期间排查了sudo、mkdir、bash命令是否已安装等问题。怀疑是环境问题,尝试将整个解压包拷贝至其他相同版本系统的机器上,发现可正常安装启动。后......
  • Delphi 修改单元名称
    我经常让GPT写一些简单的代码,它确实也能给出相对满意的结果,但是这单元的名称总是和我的不一样 我们在delphi中新建新项目名称一般都是Unit1,所以我们首先要先把Unit1修改成与GPT一样的名称才可以.首先是保存我们的新项目,然后关闭.当然里面是空白的,什么代码和控件都没加.......
  • Windows OhmGraphite 配置
    WindowsOhmGraphite配置由于windows_exporter无法监控温度相关的指标,那么就需要使用OhmGraphite进行监控该指标。下载访问https://github.com/nickbabcock/OhmGraphite/releases/地址进行下载最新的版本,下载后解压到你自己放的目录修改配置编辑OhmGraphite.exe.config文......
  • Delphi主窗体打开窗体及调用其他单元中的方法
    Delphi主窗体打开窗体及调用其他单元中的方法1、建立窗体父窗体实现父窗体点击“打开子窗体”按钮打开子窗体。点击“调用单元函数”按钮将单元方法返回信息填充到MEMO控件中。子窗体2、父窗体代码unitUnit1;interfaceusesWinapi.Windows,Winapi.Messages,Sy......
  • delphi firemonkey使用 TListbox 自定义列表数据(二StyleBook方式实现)
    上一篇用设计好界面后用代码添加稍微有些麻烦,所以改为用StyleBook设计好后添加Item界面上添加ListBox后改Item高度为100右键添加一条空白记录,观察高度,并且方便自定义编辑style样式默认添加一条ListBoxItem1Style1的样式,添加Layout布局到这个样式下,并且添加需要的控件进去la......
  • 解决 DELPHI 中执行外部命令出现屏幕一闪的问题的方法
    解决DELPHI中执行外部命令出现屏幕一闪的问题的方法有的时候我们在DELPHI中使用ShellExecuteEx(exInfo:TShellExecuteInfo)函数执行一些外部命令,但会出现,屏幕一闪的问题,解决方法如下:设置exinfo.nShow:=SW_HIDE;//隐藏命令执行的窗口,不会出现屏幕一闪的情况在exinfo......