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

小灰灰 2021-07-25 00:31 302阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.代码

### 1.题目 ###

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

### 2.代码 ###

#include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <string.h>
    
    int A[400000];
    
    int prime(int N)
    { 
      int i, j, k = 0;
      
      for (i = 2; i < N ; i++) { 
            if (N % i == 0 ) { 
                for (j = i; j < N; j += i)
                    A[j] = 1;
            }
     }
      for (i = 1; i < N; i++)
         if(!A[i])
           k++;
       return k;
    }   
    
    int main( )
    { 
        int T, N;
        scanf("%d", &T);
        while (T--) { 
        memset(A, 0, sizeof(A));
        //memset(dp, 0, sizeof(dp));
        scanf("%d", &N);
        printf("%d\n",prime(N));
        } 
        return 0;
    }

在这里插入代码片

发表评论取消回复

表情：

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

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

相关阅读

相关欧拉函数 AcWing 873. 欧拉函数

欧拉函数 AcWing 873. 欧拉函数原题链接 [AcWing 873. 欧拉函数][AcWing 873.] 算法标签数学知识欧拉函数思路

绝地灬酷狼/ 2023年09月28日 11:38/ 0 赞/ 129 阅读

相关 GuGuFishtion HDU - 6390 （欧拉函数，容斥）

GuGuFishtion \\\[ Time Limit: 1500 ms\\quad Memory Limit: 65536 kB \\\] 题意给出定义\\

Myth丶恋晨/ 2023年08月17日 17:04/ 0 赞/ 54 阅读

相关 hdu -2837(指数循环节+欧拉函数)

Problem Description Assume that f(0) = 1 and 0^0=1. f(n) = (n%10)^f(n/10) for all n big

àì夳堔傛蜴生んèń/ 2022年06月10日 13:14/ 0 赞/ 168 阅读

相关 hdu 1286 找新朋友

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

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

相关欧拉函数

定义在数论，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（φ(1)=1），例如φ(8)=4，因为1,3,5,7均和8互质。通式 ![70][

落日映苍穹つ/ 2022年05月16日 07:58/ 0 赞/ 296 阅读

相关 HDU 2824 The Euler function (欧拉函数)

The Euler function Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K

雨点打透心脏的1/2处/ 2022年03月29日 05:48/ 0 赞/ 150 阅读

相关 hdu 3501（欧拉函数引申）

题意：求小于N与N不互质的数的和欧拉公式的引伸：小于或等于n的数中，与n互质的数的总和为：φ(x) \ x / 2。(n>1) 1 include<iostre

骑猪看日落/ 2021年12月21日 01:09/ 0 赞/ 239 阅读

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

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

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

相关 HDU - 6322 - Problem D. Euler Function 【欧拉函数 + 规律】题解

目录 1.题目 2.代码 1.题目 In number theory, Euler’s totient fu

叁歲伎倆/ 2021年07月25日 00:07/ 0 赞/ 341 阅读

相关 HDU - 1787 - GCD Again 【欧拉函数】题解

目录 1.题目 2.代码 1.题目 Do you have spent some time to think

超、凢脫俗/ 2021年07月24日 12:59/ 0 赞/ 366 阅读