当前位置:首页 > 开发 > IT生活 > 正文

数论基础-欧拉函数

发表于: 2014-03-15   作者:追梦--   来源:转载   浏览:
摘要:     前几天,在杭电oj上碰到一个数论的题目,附链接: http://acm.hdu.edu.cn/showproblem.php?pid=1286     题意很简单,就是求一个数N比他小的与它互素(最大公约数为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;
}

数论基础-欧拉函数

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
POJ 3358 Period of an Infinite Binary Expansion( 数论好题 + 欧拉定理 + 欧拉函数 ) #include &l
3884: 上帝与集合的正确用法 Time Limit: 5 Sec Memory Limit: 128 MB Submit: 523 Solved: 237 [ S
给定整数n,那么n的唯一的分解式如下 欧拉函数的定义: phi(n) 为1->n中与n互素的数的个数。与n
欧拉函数: 大意:表示的是一个数有几个与它互质的数,比如8的欧拉数为4(1 3 5 7); 例题: Descr
欧拉函数Euler(x) Euler(n)表示1-n之间与n互质的个数,例如Euler(4) = 2,其中1和3与4互质。(数论里
假设C君为(0, 0), 则右上方为(n - 1, n - 1). 一个点(x, y) 能被看到的前提是gcd(x, y) = 1, 所以 a
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4483 题意:给出一个(n+1)*(n+1)的格子。在
Stern-Brocot Tree Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Ot
[Description]求值 [Solution] 不要被无限个2吓到了,这一题有一些有趣的性质可以发掘的。 这里介绍
http://poj.org/problem?id=3090 Visible Lattice Points Time Limit:1000MS Memory Limit:65536K D
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号