NYOJ 479 Coprimes

àì夳堔傛蜴生んèń 2022-08-25 01:40 47阅读 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 条评论，47人围观）

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

相关阅读

相关 479. 最大回文数乘积

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

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

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

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

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

相关 NYOJ 479 Coprimes

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

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

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

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

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

相关 hdoj 5072 Coprime 【想法+容斥原理】

题目：[hdoj 5072 Coprime][] 题意：给出n个数，然后让你从其中任意选出三个数满足其中三个数都互质或者都不互质，让你求满足这样选择条件的选择种数。

忘是亡心i/ 2022年08月07日 14:44/ 0 赞/ 29 阅读

相关 NYOJ 308

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

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

相关 NYOJ 168

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

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

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

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

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

相关 Codeforces Round #479 (Div. 3)

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

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

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

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

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