首页 > 代码库 > 找新朋友

找新朋友

2024-11-16 07:24:02   204人阅读

2017-08-03
  • https://baike.baidu.com/item/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0?fr=aladdin
  • http://baike.sogou.com/v278142.htm?fromTitle=%E8%B4%A8%E5%9B%A0%E6%95%B0
 
新年快到了，“猪头帮协会”准备搞一个聚会，已经知道现有会员N人，把会员从1到N编号，其中会长的号码是N号，凡是和会长是老朋友的，那么该会员的号码肯定和N有大于1的公约数，否则都是新朋友，现在会长想知道究竟有几个新朋友？请你编程序帮会长计算出来。

Input第一行是测试数据的组数CN（Case number，1<CN<10000），接着有CN行正整数N（1<n<32768），表示会员人数。Output对于每一个N，输出一行新朋友的人数，这样共有CN行输出。 
Sample Input

2
25608
24027

Sample Output

7680
16016

题目大意 ： 求从1——n互质的个数是多少？

题目分析 ： 正好欧拉函数正是用于求1——n的只质数个数的，所以我们直接利用欧拉函数的公式和性质即可。

题目收获 ： 欧拉函数的定义和解决类型问题，质因数的定义。

简单阐述欧拉函数和质因数的定义：

　　在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。例如φ(8)=4，因为1,3,5,7均和8互质。（现在懂得不多，之后补上）；

一般解题用到的公式通式：
　　 技术分享

　p1,p2,p3....,pn是与x的所有质因数，那我们就又要来解释下什么是质因数了。

　　质因数（ 素因数或 质因子）在数论里是指能整除给定正整数的质数。除了1以外，两个没有其他共同质因子的正整数称为 互质。比如1本身是不存在质因子的，但它又可以做

其它数的质因子。2，4,8都只有一个质因子，6有两个质因子2,3

　　质因数就是一个数的 约数，并且是 质数，比如8=2×2×2，2就是8的质因数。

代码 ：
#include <iostream>
#include <set>
using namespace std;

int eular(int x)
{
    int  res = x;
    for (int i = 2; i < (int)sqrt(x *1.0) + 1; i++)
    {
        if (x % i == 0)//i是否为质因子
        {
            res = res / i * (i - 1);
            while (x % i == 0)//求不同的质因子
                x /= i;
        }
    }
    if (x > 1)//本身是质数的情况。
        res = res / x * (x - 1);
    return res;
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int a;
        cin >> a;
        cout << eular(a) << endl;
    }
    return 0;
}

 



 
找新朋友






























        

            
                
                  
                
                

                    联系

                    我们