NYOJ 479 Coprimes

àì夳堔傛蜴生んèń 2022-08-25 01:40 21阅读 0赞

## Coprimes ##

时间限制： 500 ms | 内存限制： 4096 KB

难度： 1

描述

For given integer N (1 <=N <=10 4) find amount of positive numbers not greater than N that coprime with N. Let us call two positive integers (say, A and B, for example) coprime if (and only if) their greatest common divisor is 1. (i.e. A and B are coprime iff gcd(A,B) = 1).

输入

Input file contains integer N.（ 注意：程序以文件结束符“EOF”结束输入。）

输出

Write answer in output file. 每个数字占一行。

样例输入

9

样例输出

6

思路：题目比较简单，就是求n以内与n的最大公约数为1的数的个数。

#include <stdio.h>
    
    int gcd(int m, int n)
    {
    	int r = n;
    	while (r != 0)
    	{
    		r = m % n;
    		m = n;
    		n = r;
    	}
    	return m;
    }
    
    int main()
    {
    	int i,n;
    	while (scanf("%d",&n) != EOF)
    	{
    		int total = 0;
    		for (i=1; i<n; i++)
    		{
    			if (gcd(i,n) == 1)
    			{
    				total++;
    			}
    		}
    		printf("%d\n",total);
    	}
    	return 0;
    }

如果一个质数p整除n，那么当前就有(1-1/p)个数与它的最大公约数不被p整除，累乘即可得出结果。

#include <stdio.h>
    
    int main(void)
    {
        int i,n,total;
        while (scanf("%d", &n) != EOF)
    	{
    		total = n;
    		for (i=2; i<=n; i++)
    		{
    			if (n % i == 0)
    			{
    				total = total / i * (i-1);
    			}
    			while (n % i == 0)
    			{
    				n /= i;
    			}
    		}
    		printf("%d\n",total);
    	}
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 479. 最大回文数乘积

> 你需要找到由两个 n 位数的乘积组成的最大回文数。 > > 由于结果会很大，你只需返回最大回文数 mod 1337得到的结果。 > > 示例: > > 输入:

「爱情、让人受尽委屈。」/ 2022年10月16日 12:23/ 0 赞/ 196 阅读

相关 479 加分二叉树（区间dp）

1. 问题描述：设一个 n 个节点的二叉树 tree 的中序遍历为（1，2，3，…，n），其中数字 1，2，3，…，n 为节点编号。每个节点都有一个分数（均为正整数），记第

╰+哭是因爲堅強的太久メ/ 2022年09月13日 00:21/ 0 赞/ 137 阅读

相关 NYOJ 479 Coprimes

Coprimes 时间限制： 500 ms | 内存限制： 4096 KB 难度： 1 描述 For given integer N (1 <=N <=10 4)

àì夳堔傛蜴生んèń/ 2022年08月25日 01:40/ 0 赞/ 22 阅读

相关 codeforces 479B. Towers C - Exams【排序】

题目：[codeforces 479B. Towers ][codeforces 479B. Towers] 题意：给出一个长度 n 的序列，最多可以有 k 次操作

ゝ一纸荒年。/ 2022年08月10日 12:49/ 0 赞/ 30 阅读

相关 NYOJ 308

Substring 时间限制： 1000 ms | 内存限制： 65535 KB 难度： 1 描述 You are given a string input.

客官°小女子只卖身不卖艺/ 2022年06月17日 13:20/ 0 赞/ 181 阅读

相关 NYOJ 168

房间安排时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述 2010年上海世界博览会(Expo2010),是第41届世界博览会。于

冷不防/ 2022年06月17日 05:53/ 0 赞/ 188 阅读

相关 NYOJ 541

最强DE 战斗力时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述春秋战国时期，赵国地大物博，资源非常丰富，人民安居乐业。但许多

Myth丶恋晨/ 2022年06月16日 03:48/ 0 赞/ 211 阅读

相关 HDU-5072 Coprime(容斥原理，同色三角形)

Coprime HDU - 5072 -------------------- There are n people standing in a line. Eac

矫情吗；*/ 2022年06月09日 01:11/ 0 赞/ 188 阅读

相关 Codeforces Round #479 (Div. 3)

D:[Divide by three, multiply by two][Divide by three_ multiply by two] 除了这种做法还可以通过建图

￡神魔★判官ぃ/ 2022年05月24日 20:59/ 0 赞/ 207 阅读

相关 Codeforces Round \#479 (Div. 3)（题解）

A. Wrong Subtraction 题意：给出一个数字n，然后进行k次操作，每次在n的个位上减1，如果个位是0的话，去掉这一位，继续操作，输出最后结果

分手后的思念是犯贱/ 2022年05月24日 10:14/ 0 赞/ 198 阅读