[Jobdu] 题目1493：公约数

末蓝、 2021-12-03 07:27 87阅读 0赞

**题目描述：**

给定两个正整数a，b（1<=a,b<=100000000）,计算他们公约数的个数。  
如给定正整数8和16，他们的公约数有：1、2、4、8，所以输出为4。

**输入：**

输入包含多组测试数据，每组测试数据一行，包含两个整数a，b。

**输出：**

对于每组测试数据，输出为一个整数，表示a和b的公约数个数。

**样例输入：**

8 16
    22 16

**样例输出：**

4
    2

五星级题目，其实就是考察对程序的优化，公约数的约数肯定也是他们的公约数！我们只要遍历从找1到sqrt(gdc)的公约数就行，注意这里要加上2！因为在sqrt(x)到x区间还有一个约数！还有就是注意边界特例！

1 #include <iostream>
     2 using namespace std;
     3  
     4 int gcd(int a, int b) {
     5     int m = a > b ? a : b;
     6     int n = a > b ? b : a;
     7     return n == 0 ? a : gcd(n, m % n);
     8 }
     9  
    10 int main() {
    11     int a, b;
    12     int max;
    13     int count;
    14     int i;
    15     while (cin >> a >> b) {
    16         count = 0;
    17         max = gcd(a, b);
    18         for (i = 1; i * i < max; ++i) {
    19             if (max % i == 0)
    20                 count += 2;
    21         }
    22         if (i * i == max) 
    23             ++count;
    24         cout << count << endl;
    25  
    26     }
    27     return 0;
    28 }
    29 /**************************************************************
    30     Problem: 1493
    31     User: hupo250
    32     Language: C++
    33     Result: Accepted
    34     Time:30 ms
    35     Memory:1520 kb
    36 ****************************************************************/

转载于:https://www.cnblogs.com/easonliu/p/3657334.html

发表评论取消回复

表情：

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

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

相关阅读

相关南阳题目40-公约数和公倍数

公约数和公倍数时间限制： 1000 ms | 内存限制： 65535 KB 难度： 1 描述小明被一个问题给难住了，现在需要你帮帮忙。问题是：给出两个正整数，求

阳光穿透心脏的1/2处/ 2022年07月27日 13:34/ 0 赞/ 56 阅读

相关【POJ】1493

如此水题，竟然让我蛋疼不已，留念 include<iostream> include<vector> include<algorithm>

逃离我推掉我的手/ 2022年05月29日 06:46/ 0 赞/ 50 阅读

相关 [数据结构][Python][经典题目]最大公约数

方案1 辗转相除法，又名欧几里得算法。定理：两个正整数a和b（a>b)，他们的最大公约数等于a除以b 的余数c和b之间的最大公约数。 def get_gr

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

相关 [Jobdu] 题目1377：缓变序列

题目描述：陈博在写论文时碰到一个难题：如何将给定的整数序列变换成缓变序列：即任意两个相邻的元素相差均为1，第1个元素和最后一个元素相差也为1. 变换是指改变原整数序列中各元

偏执的太偏执、/ 2021年12月03日 07:31/ 0 赞/ 104 阅读

相关 [Jobdu] 题目1504：把数组排成最小的数

题目描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组\{3，32，321\}，则打印出这三个数字能排成的最小数

迈不过友情╰/ 2021年12月03日 07:29/ 0 赞/ 138 阅读

相关 [Jobdu] 题目1522：包含min函数的栈

题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。输入：输入可能包含多个测试样例，输入以EOF结束。对于每个测试案例，输入的第一

我不是女神ヾ/ 2021年12月03日 07:27/ 0 赞/ 132 阅读

相关 [Jobdu] 题目1493：公约数

题目描述：给定两个正整数a，b（1<=a,b<=100000000）,计算他们公约数的个数。如给定正整数8和16，他们的公约数有：1、2、4、8，所以输出为4。输

末蓝、/ 2021年12月03日 07:27/ 0 赞/ 88 阅读

相关 [Jobdu] 题目1283：第一个只出现一次的字符

题目描述：在一个字符串(1<=字符串长度<=10000，全部由大写字母组成)中找到第一个只出现一次的字符。输入：输入有多组数据每一组输入一个字符串。输出：

灰太狼/ 2021年12月03日 07:25/ 0 赞/ 225 阅读

相关 Java 计算公约数和最大公约数

package java_1; import java.util.Scanner; public class Exercises_3

清疚/ 2021年11月02日 09:14/ 0 赞/ 349 阅读

相关 [Jobdu] 题目1420：Jobdu MM分水果

题目描述： Jobdu团队有俩PPMM，这俩MM干啥都想一样。一天，富强公司给团队赞助了一批水果，胡老板就把水果派发给了这俩MM，由她们自行分配。每个水果都有一个重量，你能告

- 日理万妓/ 2021年09月30日 00:22/ 0 赞/ 150 阅读