hdu-1286 找新朋友(欧拉函数,水题)
2024-08-25 12:40:42
题目链接:
找新朋友
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10120 Accepted Submission(s): 5344
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
AC代码:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+;
int phi[N];
int get_phi()
{
for(int i=;i<N;i++)
{
if(!phi[i])
{
for(int j=i;j<N;j+=i)
{
if(!phi[j])phi[j]=j;
phi[j]=phi[j]/i*(i-);
}
}
}
}
int main()
{
get_phi();
int a,b,n;
scanf("%d",&n);
while(n--)
{
int x;
scanf("%d",&x);
cout<<phi[x]<<"\n";
}
return ;
}
最新文章
- SoapUI 设置 request data with json body
- jrebel注意事项
- Django~学习计划
- Java-->;打包发送信息(UDP协议)
- XidianOJ 1097 焊板子的xry111
- VS SuppressMessage忽略特定方法的警告信息
- ARC以及MRC中setter方法
- 学习ios键盘和textfield之间操作体会
- Android Studio中获取sha1证书指纹数据的方法
- 跨域访问之JSONP
- RocketMQ快速入门
- 关于python中argsort()函数的使用
- ACE之通信的设计空间
- django(权限、认证)系统——用户Login,Logout
- Docker Toolbox
- 组件、框架、Packagist、Composer
- 【python40--类和对象:一些相关的BIF】
- android 中解析json格式数据
- uva 10983 Buy one, get the rest free 二分判定层次图
- Andrew Ng机器学习第三章——线性回归回顾