`
追梦--
  • 浏览: 38041 次
  • 性别: Icon_minigender_1
社区版块
存档分类
最新评论

数论基础-欧拉函数

阅读更多
    前几天,在杭电oj上碰到一个数论的题目,附链接: http://acm.hdu.edu.cn/showproblem.php?pid=1286
    题意很简单,就是求一个数N比他小的与它互素(最大公约数为1)的数有多少个。
    刚开始想要暴力的方法去解决这个问题,但后来发现暴力的时间复杂度是O(n^2),而N是32768以内的整数,测试数据有10000组,明显暴力会超时。
    后来教练讲了下,说这种题目要用欧拉函数解决,一个很裸的水题。
    这里介绍下欧拉函数
     Phi(n)=n(1-1/p1) (1-1/p2)….. (1-1/pk)
     其中p1, p2 ,pk是n的所有素数因子
     Phi(n):所有小于等于n的且与n互素的数的个数
    有了这个定理,这道题的确很容易了(以前没怎么接触数论的题TT)
下面贴代码:
#include<stdio.h>
#include<math.h>
int prime[3600],isprime[32768];
int primeNum;
int findPrime(){
    primeNum = 0;
    for(int i=2;i<32768;i++){
       if(isprime[i]) continue;
       prime[primeNum++] = i;
       for(int j=i*i;j<32768;j+=i)
          isprime[j] = 1;
    }
    return 0;
}
int main(){
    findPrime();
    int t;
    scanf("%d",&t);
    while(t--){
       int n;
       scanf("%d",&n);
       double tmp = n;
       int p = 0;
       while(n!=1){
          if(n%prime[p]==0){
             tmp *=1-1.0/prime[p];
             while(n%prime[p]==0)
                n /= prime[p];
          }
          p++;
       }
       printf("%d\n",(int)round(tmp));
    }
    return 0;
}
分享到:
评论

相关推荐

    算法-数论- 欧拉函数.rar

    此外,欧拉函数还可以用于计算循环群的阶,这在群论中是基础概念。一个循环群的阶就是它的元素个数,而这个数量可以通过欧拉函数得到。 总之,欧拉函数作为数论的一个核心概念,它的理论和应用贯穿于许多数学分支。...

    讲义204-第二章第四讲-欧拉函数的计算(2023-1005,周四34).pdf

    欧拉函数,记作(),是数论中的一个重要函数,它表示小于或等于的正整数中与互素的数的个数。换句话说,()计算的是集合{0, 1, ..., - 1}中与的最大公约数为1的元素数量。这个函数在数论的许多领域都有应用,如同余类...

    初等数论中求欧拉函数值程序

    欧拉函数在数论中扮演着关键角色,因为它与许多其他数论问题紧密相关,如模运算、同余类、素数分布以及费马小定理。费马小定理指出,如果p是素数且a与p互质,那么a^(p-1) ≡ 1 (mod p)。这个定理可以推广到欧拉定理...

    初等数论---------------------教材整理-新课标其它.zip

    例如,欧拉函数φ(n)表示小于或等于n且与n互质的正整数的数量,这对理解数的可除性有着重要意义。此外,还有完全平方数的检测方法,如费马小定理,它指出如果p是质数且a不是p的倍数,则a^(p-1) ≡ 1 (mod p)。 在...

    (1.1.7)--欧拉简介1

    在代数领域,欧拉发现了实系数多项式分解的基本定理,还给出了费马小定理的证明,引入了数论中的欧拉函数,促进了数论的独立发展。 欧拉在几何学上也有卓越贡献,他解决了著名的哥尼斯堡七桥问题,这不仅展示了他的...

    欧拉函数公式以及证明

    欧拉函数是数论中很重要的一个函数,欧拉函数是指:对于一个正整数 n ,小于 n 且和 n 互质的正整数(包括 1)的个数,记作 φ(n) 。 完全余数集合: 定义小于 n 且和 n 互质的数构成的集合为 Zn ,称呼这个集合为...

    组合数学 实现 欧拉函数 cayley定理 等

    这里我们将详细探讨标题和描述中提到的几个关键概念:欧拉函数、Cayley定理、Mobius定理以及整数拆分。 1. **欧拉函数**(Euler's totient function): 欧拉函数φ(n)定义为小于n且与n互质的正整数的数量。它是...

    线性素筛 欧拉函数 区间筛素数.zip_sowoc_算法 欧拉函数 线性筛

    欧拉函数,通常用φ(n)表示,是一个数论函数,它给出了小于或等于n的正整数中与n互质的数的数量。欧拉函数在密码学、组合数学和计算理论中扮演着核心角色,因为它的性质与模运算和群论密切相关。 线性素筛和欧拉...

    欧拉函数的几个性质及证明.pdf

    欧拉函数(Euler's totient function),通常表示为φ(n),是数论中一个非常重要的函数。它定义为在1到n之间(包含1和n)与n互质的正整数个数。例如,φ(1)=1,因为只有1与1互质;φ(2)=1,因为只有1与2互质;φ(3)=...

    代码实现,欧拉函数代码实现,matlab

    欧拉函数,通常用φ(n)表示,是计算小于或等于n且与n互质的正整数的数量,它在数论中具有重要的地位。MATLAB是一种强大的数学计算软件,适合进行这种数学运算的编程。 欧拉函数的实现通常涉及到质因数分解和循环...

    算法-欧拉定理(洛谷-P5091)(扩展欧拉定理实现)(包含源程序).rar

    欧拉定理的一般形式是:如果\(a\)、\(m\)是两个互质的正整数,则对于任意非零整数\(n\),有\(a^{\phi(m)} \equiv 1 \pmod{m}\),其中\(\phi(m)\)是欧拉函数,表示小于或等于\(m\)且与\(m\)互质的正整数的数量。...

    简化剩余系和欧拉函数.ppt

    在数论的广阔天地中,欧拉函数和简化剩余系如同两颗璀璨的明珠,它们在理论研究和实际应用中都占据着举足轻重的位置。欧拉函数 φ(n) 是一个计数函数,它描述了在1到n的所有正整数中,与n互素的正整数的个数。互素...

    欧拉函数 1

    欧拉函数是一种_IMPORTANT_函数在数论中,它表示 1 到 n-1 之间,与 n 互质的数的个数。在本篇文章中,我们将详细介绍欧拉函数的定义、计算方法和应用场景。 定义 欧拉函数 phi(n) 是指 1 到 n-1 之间,与 n 互质的...

    扩展欧几里得、模幂运算、欧拉函数

    欧拉函数在数论中具有许多重要性质,如欧拉定理:如果a与n互质,则a^φ(n) ≡ 1 (mod n)。欧拉函数对于理解群论中的原根、计算离散对数和在RSA公钥密码系统中确定安全密钥大小都有关键作用。 现在,我们来看压缩包...

    算法-欧拉定理(洛谷-P5091)(十进制快速幂实现)(包含源程序).rar

    欧拉定理表述如下:如果a和n是正整数,且它们互为质数(即最大公约数为1),那么a的φ(n)次方除以n的余数等于1,其中φ(n)是欧拉函数,表示小于或等于n的正整数中与n互质的数的数量。欧拉定理可以用来简化模指数运算...

    数论学习系列之取整函数.pdf

    在数论中,取整函数经常被用来定义其他函数,比如欧拉函数、莫比乌斯函数等。它也是研究素数分布、整数划分等数论问题的基础工具之一。例如,研究素数的定理——素数定理,就可以用取整函数来表达,它说明了不大于...

    ACM-数论基础_张君达编

    初等数论是数学的一个分支,专注于研究整数的性质,它是数学中最古老和最基础的领域之一。早在公元前3世纪,古希腊数学家欧几里德便证明了素数有无穷多个,这是数论的一个重要成就。中国古代的《孙子算经》中也包含...

    hdu 1695 GCD(欧拉函数+容斥原理).docx

    "hdu 1695 GCD(欧拉函数+容斥原理)" 题目大意是:给定 a, b, c, d, k,找到一队 x, y,满足 g(x, y) = k,且 x ∈ [1...这道题目考察了欧拉函数、容斥原理和筛法等数论知识,并且需要使用编程技巧来实现高效的计算。

    96、OI(信奥)中的数论-2020.06.09.rar

    2. 欧拉定理:若a与m互质,则a^φ(m) ≡ 1 mod m,其中φ(m)是欧拉函数,表示小于等于m且与m互质的正整数个数。 五、线性同余方程 1. 莫比乌斯反演:一种强大的数论工具,用于解决涉及乘积的问题,如计算非负整数的...

    Euler函数前缀

    本主题聚焦于"欧拉函数前缀",这是一个在数论和计算理论中常见的概念,尤其在解决一些算法问题时非常有用。欧拉函数,通常用φ表示,是数论中的一个基本函数,它对于正整数n,给出了小于或等于n且与n互质的正整数的...

Global site tag (gtag.js) - Google Analytics