首页 > 其他分享 >欧拉函数

欧拉函数

时间:2022-12-22 22:23:14浏览次数:35  
标签:函数 int res ll maxn 欧拉

欧拉函数模板
点击查看代码
ll euler(ll n)  //返回euler(n)
{
    ll res=n,a=n;
    for(ll i=2; i*i<=a; 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);
    return res;
}
筛法求欧拉函数模板
点击查看代码
int check[maxn],phi[maxn],prime[maxn];
int main()
{
    int n,cnt=0;
    n=maxn;
    phi[1]=1;
    for(int i=2; i<=n; i++)
    {
        if(!check[i])
        {
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1; j<=cnt&&prime[j]*i<=n; j++)
        {
            check[i*prime[j]]=1;
            if(i%prime[j])
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            else
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
        }
    }
}

1~n中与n互质的数的和: n/2 * φ(n) (n>1), 1 (n=1)
即不与n互质的数的和:n/2 * (n+1)-n/2 * φ(n)(n>1),0 (n=1)

标签:函数,int,res,ll,maxn,欧拉
From: https://www.cnblogs.com/wujw11world/p/16999714.html

相关文章

  • 2022年能让你早点下班的36个JavaScript实用函数!
    携手创作,共同成长!这是我参与「掘金日新计划·8月更文挑战」的第17天,点击查看活动详情之前在掘金写了一篇介绍JavaScript小技巧的文章,很受大家欢迎。但是有朋友说还......
  • C++学习---cstdio的源码学习分析10-改变文件流文件流buffer函数setvbuf
    cstdio中的文件访问函数stdio.h中定义了一系列文件访问函数(fopen,fclose,fflush,freopen,setbuf,setvbuf),接下来我们一起来分析一下setvbuf对应的源码实现。-fopen:打开文件-......
  • 【Unity】基于波函数坍塌算法实现赛道自动化生成
    前言:很久没有写博客了,最近忙里偷闲准备恢复写博客的习惯,一是整理之前的笔记,二是梳理下知识点以供回顾。想写的内容很多,准备先针对以往做过的项目写个总结,最近在网上看到利......
  • jmeter的函数使用
    JMeter提供了很多函数,如果能够熟练使用,可以为脚本带来很多方便。JMeter函数是一种特殊值,可用于除测试计划外的任何组件。函数调用的格式如下所示:${__functionName(var1,var2......
  • 递规之三——完整的科目名称(Excel函数集团)
    使用了递规的Lambda,参数必须是序列数吗?当然不是!来看看这个例子:根据科目代码和科目名称,用公式完成完整的科目名称 自定义的名称是Itm,Itm的参数是Lambda中定义的参数x,......
  • 递规之二(Excel函数集团)
    递规,应该算是个数学问题吧,但它并不只能解决数学问题,还可以解决Excel里的迭代问题。ExcelHome的系列丛书之一,《Excel2019函数与公式应用大全》的第481页示例25-4,就是一个带......
  • 递规之一(Excel函数集团)
    递规,这名词出现在了Excel函数集团,是的,你没看错!但递规在工作表函数里,也不是无限制的用,而是有以下条件:需要Lambda出马需要一个起始开关需要自定义名称先祭一个最简单......
  • Bash Shell自定义助手函数git-submodule-foreach:遍历对每个子模块仓库执行自定义的函
    BashShell自定义助手函数git-submodule-foreach:遍历对每个子模块仓库执行自定义的函数或命令序列...概述:在一个大型项目下,我们通常通过GitSubmodule(子模块)机制引入了其......
  • Go 快速入门指南 - 函数
    概述函数 是将一个或者一类问题包装为一个代码块,可以被多次调用,提高代码重用性。Go函数中声明、定义、参数、返回值这些基础概念,和其他编程语言中的一致,这里不再赘述。......
  • Go 快速入门指南 - init 函数
    概述init()函数 是一个特殊的函数,一般称为初始化函数,不能被调用。 在每个文件里面,当程序启动或者文件被作为包引用的时候,init()函数就会自动执行,一般用来做一些包的......