本文共 1010 字,大约阅读时间需要 3 分钟。
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4168 Accepted Submission(s): 1894
Problem Description
新年快到了,“猪头帮协会”准备搞一个聚会,已经知道现有会员N人,把会员从1到N编号,其中会长的号码是N号,凡是和会长是老朋友的,那么该会员的号码肯定和N有大于1的公约数,否则都是新朋友,现在会长想知道究竟有几个新朋友?请你编程序帮会长计算出来。
Input
第一行是测试数据的组数CN(Case number,1<CN<10000),接着有CN行正整数N(1<n<32768),表示会员人数。
Output
对于每一个N,输出一行新朋友的人数,这样共有CN行输出。
#include#include using namespace std; const int BF = 32768; int main() { int n; scanf("%d",&n); while(n--){ bitset bs(0); int value; scanf("%d",&value); for (int i = 2; i <= value / 2; ++i) { if (value % i == 0){ for (int j = i; j < value; j+=i) bs.set(j); } } printf("%d\n",value - bs.count() - 1); } return 0; }
解题思路
:if (num % i == 0)
(其中i>=2) 表示是老朋友,将i
的老盆友
从i*2
…i*n < num
全标记,最后newfrind = num - bs.cont(老盆友) - 1(自己)
;
转载地址:http://ttgbb.baihongyu.com/