hdu 1286 找新朋友

冷不防 2022-05-31 09:46 186阅读 0赞

# 找新朋友 #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 14409 Accepted Submission(s): 7717**

Problem Description

新年快到了，“猪头帮协会”准备搞一个聚会，已经知道现有会员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

Author

SmallBeer(CML)

Source

[杭电ACM集训队训练赛（VII）][ACM_VII]

题目解析：

这个题目是一个非常简单的欧拉函数的模板题目，直接看代码把，这个代码可以直接当欧拉函数模板，1A

代码：

#include <bits/stdc++.h>
    using namespace std;
    
    int euler(int n)
    {
        int ans=1;
        int i;
        for(i=2; i*i<=n; i++)
        {
            if(n%i==0)
            {
                n/=i;
                ans*=i-1;
                while(n%i==0)
                {
                    n/=i;
                    ans*=i;
                }
            }
        }
        if(n>1)
            ans*=n-1;
        return ans;
    }
    int main()
    {
        int T;
        cin>>T;
        while(T--)
        {
            int n;
            cin>>n;
            cout<<euler(n)<<endl;
        }
        return 0;
    }

[ACM_VII]: http://acm.hdu.edu.cn/search.php?field=problem&key=%BA%BC%B5%E7ACM%BC%AF%D1%B5%B6%D3%D1%B5%C1%B7%C8%FC%A3%A8VII%A3%A9&source=1&searchmode=source

发表评论取消回复

表情：

评论列表（有 0 条评论，186人围观）

还没有评论，来说两句吧...

相关阅读

相关找女朋友

找女朋友 Time Limit: 15ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述山东理工大学有很多学生，当然也

桃扇骨/ 2022年09月25日 08:29/ 0 赞/ 193 阅读

相关找女朋友

找女朋友 Time Limit: 15ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述山东理工大学有很多学生，当然也有很多美

拼搏现实的明天。/ 2022年08月10日 06:08/ 0 赞/ 215 阅读

相关找朋友（bfs）

Problem Description X，作为户外运动的忠实爱好者，总是不想呆在家里。现在，他想把死宅Y从家里拉出来。问从X的家到Y的家的最短时间是多少。为了简化问题

谁借莪１个温暖的怀抱￠/ 2022年07月12日 11:44/ 0 赞/ 176 阅读

相关找朋友

建议使用字符数组去建立矩阵，不要用int类型的，容易wrong answer Problem Description X，作为户外运动的忠实爱好者，总是不想呆在家里

向右看齐/ 2022年07月12日 07:50/ 0 赞/ 208 阅读

相关找朋友

建议使用字符数组去建立矩阵，不要用int类型的，容易wrong answer Problem Description X，作为户外运动的忠实爱好者，总是不想呆在家里

爱被打了一巴掌/ 2022年07月12日 07:50/ 0 赞/ 174 阅读

相关 sdut ——找朋友（广度优先搜索）

think: 1今天上午做了一上午才AC这个题目，感觉后台数据有非法输入，一开始自己用的int型map数组通过输入的字符的四种情况来判断map的值，可是样本数据正确提交却一

深藏阁楼爱情的钟/ 2022年07月12日 07:25/ 0 赞/ 119 阅读

相关 hdu 1286 找新朋友

找新朋友 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

冷不防/ 2022年05月31日 09:46/ 0 赞/ 187 阅读

相关 C-K要找女朋友

Problem Description 临近11.11，CK看见周围的朋友一个个的都脱单或者正准备脱单了，CK也想要找一个女朋友了（听说国家会分配？）。MeiK听说了这件事情

左手的ㄟ右手/ 2022年04月13日 09:26/ 0 赞/ 227 阅读

相关 hdoj1286

找新朋友 \include<iostream> \include<string.h> \include<stdio.h> using namespace st

落日映苍穹つ/ 2021年11月22日 08:56/ 0 赞/ 131 阅读

相关 HDU - 1286 - 找新朋友【欧拉函数】题解

目录 1.题目 2.代码 1.题目新年快到了，“猪头帮协会”准备搞一个聚会，已经知道现有会员N人，把会员从

小灰灰/ 2021年07月25日 00:31/ 0 赞/ 289 阅读