其它综合

hdu-1286找新朋友(欧拉函数,水题)

我爱IT资讯库   2021/02/23

题目链接:

找新朋友

time limit: 2000/1000 ms (java/others)memory limit: 65536/32768 k (java/others)
total submission(s): 10120accepted submission(s): 5344


problem description

新年快到了,猪头帮协会准备搞一个聚会,已经知道现有会员n人,把会员从1到n编号,其中会长的号码是n号,凡是和会长是老朋友的,那么该会员的号码肯定和n有大于1的公约数,否则都是新朋友,现在会长想知道究竟有几个新朋友?请你编程序帮会长计算出来。

input

第一行是测试数据的组数cn(case number,1lt;cnlt;10000),接着有cn行正整数n(1lt;nlt;32768),表示会员人数。

output

对于每一个n,输出一行新朋友的人数,这样共有cn行输出。

sample input

2

25608

24027

sample output

7680

16016

ac代码:

#include lt;iostreamgt;
#include lt;cstringgt;
#include lt;cstdiogt;
#include lt;algorithmgt;
using namespace std;
const int n=1e5+3;
int phi[n];
int get_phi()
{
    for(int i=2;ilt;n;i++)
    {
        if(!phi[i])
        {
            for(int j=i;jlt;n;j+=i)
            {
                if(!phi[j])phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
        }
    }
}
int main()
{
    get_phi();
    int a,b,n;
    scanf("%d",amp;n);
    while(n--)
    {
        int x;
        scanf("%d",amp;x);
        coutlt;lt;phi[x]lt;lt;"\n";
    }
    return 0;
}

hdu-1286 找新朋友(欧拉函数,水题)

原文地址:http://www.cnblogs.com/zhangchengc919/p/5274253.html




热门内容

java程序 处理 andrid本地帮助文档打开慢的方式

    下载本地的android自带sdk帮助文档由于有被墙的google地址,可以通... ...

RTTI学习笔记

翻看C++的书,对RTTI的讲解都很困惑,"你知道你的对象是哪个类吗","RTTI常用于调试和数据库程序"对这些讲... ...

使用axis2传输附件

服务端Service文件: import java.io.FileOutputStream; import jav... ...

sql server 的行转列

sql server中行转列在sql2005之后,sqlserver引入了pivot运算符,也即是可以旋转行为列,... ...
【Node.js基础篇】(九)使用readline模块实现Node.js的输入输出

【Node.js基础篇】(九)使用readline模块实现Node.js的输入输出

学C++的时候,有cout和cin,Java也有println和Scanner控件,Node.js也有如同... ...
iOS 应用支持4寸屏

iOS 应用支持4寸屏

iPhone 5出了,一大批应用要兼容新的分辨率,下载了Xcode 4.5,在官方那里找不到有关兼容新分辨... ...

循环执行oracle到mysql的迁移步骤及各种注意事项

改章节笔者在北京逛街的时候突然想到的...今天就有想写几篇关于循环执行的笔记,所以回家到之后就奋笔疾书的写出来发表了 ... ...
2015收获的季节

2015收获的季节

—————————————————————前言————————————————————— ———————... ...

JSP中的pageEncoding和contentType属性

关于JSP页面中的pageEncoding和contentType两种属性的区别: pageEncoding是js... ...

对XX证券报关于物联网操作系统的几个问题的答复

XX证券报提问了几个关于物联网和物联网操作系统的问题,个人表达了一些粗陋的观点,在这里发表出来,与行业朋友交流和探... ...
In语句优化

In语句优化

In语句的优化 现有两张表: CLINIC_ORGANISM 数据量:1400 LAB_DRUGRESISTITE... ...
fuzzysearch, 在JavaScript中,快速而快速的模糊搜索

fuzzysearch, 在JavaScript中,快速而快速的模糊搜索

源代码名称:fuzzysearch源代码网址:http://www.github.com/bevacqua/fuzzys ...

SQL Server里的 ISNULL 与 NULLIF

SQL Server 中有两个参数,语法:     ISNULL(check_... ...

判断SD是否存在及其容量查询

这个非常简单,直接上代码: MainActivity: package com.home.getsdinf... ...

Python:如何排序(sort)

一、前言 python的列表(list)有两个排序方法: 一种是内建的list.sort()方法,可以直接改变列表的内容 ...

boost库在工作(5)作用域智能指针scoped_ptr之四

第二种情况,主要就是使用在调用异常抛出的函数的地方。如下面的例子: //异常抛出的函数,适合使用智能指针... ...

Error:couldnotopen`C:\ProgramFiles\Java\jre6\lib\i386\jvm.cfg'

昨天刚过情人节!哈哈,好久没记录学习内容了,今天在房子闲着没事重新安装jdk,按道理很简单的; 第一步下载jdk; ...

第49周二

晚上总结下今天,主要是在完善用户需求文档,同时看了jquery相关的操作技巧,主要是想学习jquery源码,在知乎jqu ...

C++ #include 和 using std::string

今天,偶尔写了一个小小的程序,关于字符串问题程序。 比如,我想连续打印用户输入的字符串。 #include&l... ...

Struts Hibernate Spring 经典面试题

Hibernate工作原理及为什么要用? 原理: 1.读取并解析配置文件 2.读取并解析映射信息,创建Ses... ...

SAP Performance浅析

本文来源于:http://scnblogs.techweb.com.cn/tcsapbw/archives/106... ...

数据库MySQL与xls文件的互导

      最近的一个项目需要将xls表导入到MySQL数据库中和将MySQL数据表导出到... ...

Head-of-Line Blocking (线头阻塞)

Head of Line (HOL) Blocking 产生的原因: 概念:队列的首个packet由于它的目的... ...

Python set的高效利用

python set的应用   ... ...

CollectionFrameWork

collectionframework如下: collection ├list │├linkedlist │├array ...

JAVA访问修饰符构造函数的问题(转)

java访问修饰符 构造函数的问题 java访问修饰符-限定符总结(类比c#) java访问修饰符--------- ...

PAT甲1004CountingLeaves【dfs】

1004counting leaves(30 分) a family hierarchy is usually p ...

171.[LeetCode]Excel Sheet Column Number

题目: Related to question Excel Sheet Column Title ... ...

在.NET中获取一台电脑名,IP地址及当前用户名

在.NET中获取一台电脑名,IP地址及当前用户名是非常简单,以下是我常用的几种方法,如果大家还有其他好的方法,可以回复一... ...
sun directory server

sun directory server

Sun One Directory Server(LDAP)安装和调整指南   ... ...