Dotcpp > 试卷列表 > （最大公约数之和）下列程序想要求解整数 n的所有约数两

（最大公约数之和）下列程序想要求解整数 n的所有约数两

"NOIP真题" 试卷中 NOIP第二十四届全国青少年信息学奥林匹克联赛初赛试题[2018普及组] 中有题目如下：

（最大公约数之和）下列程序想要求解整数 n 的所有约数两两之间最大公约数的和对10007 求余后的值，试补全程序。

举例来说，4 的所有约数是 1,2,4。1 和 2 的最大公约数为 1；2 和 4 的最大公约数为 2；1 和 4 的最大公约数为 1。于是答案为 1 + 2 + 1 = 4。

要求 getDivisor 函数的复杂度为 O(√n)，gcd 函数的复杂度为O(log max(a,b))。

例如:

#include <iostream>
using namespace std;
const int N = 110000, P = 10007;
int n;
int a[N], len;
int ans;
void getDivisor() {
    len = 0;
    for (int i = 1; ① <= n; ++i)
        if (n % i == 0) {
            a[++len] = i;
            if ( ② != i) a[++len] = n / i;
        }
    }
}
int gcd(int a, int b) {
    if (b == 0) {
        ③ ;
    }
    return gcd(b, ④ );
}
int main() {
    cin >> n;
    getDivisor();
    ans = 0;
    for (int i = 1; i <= len; ++i) {
        for (int j = i + 1; j <= len; ++j) {
            ans = ( ⑤ ) % P;
        }
    }
    cout << ans << endl;
    return 0;
}

共 14 分　

所属试卷：NOIP第二十四届全国青少年信息学奥林匹克联赛初赛试题[2018普及组]

其它题目

在定义函数模板或类模板时，开头的保留字是

派生类的构造函数的成员初始化列中，不能包含。

下列程序的执行结果是（）。

设有：则调用函数scanf能正确给s和c读入数据的是

使用运算符测试集合包含集合A是否为集合B的真子集的表达

表达式{1，2，3}<{1，2，4}的值为______

已知x={‘a’:’b’,’c’:’d’}，那么表达式

字符串“ab\n\\012\\\”的长度是______

给定程序中，函数fun的功能是：将N╳N矩阵主对角线元

在客户/服务器结构中，应用程序运行在。

数据库的恢复是以 ___ 为基础的。

下面（）不属于数据库管理系统。

设关系R(A,B,C)和关系S(B,C,D)，则下列各

在数据库的三级模式结构中，描述数据库中局部逻辑结构和特

用不带头结点的单链表存储队列时,其队头指针指向队头结点

有关集线器说法不正确的是

SQL语言是( )的语言，轻易学习。

对空栈 S 进行 Push 和 Pop 操作，入栈序列

一棵有 n 个结点的完全二叉树用数组进行存储与表示，已

若有以下数组a，数组元素：a[0]~a[9]，其值为9

设(k=a=5,b=3,a*b)，则k值为_____。

若有定义语句：char*s1="OK"，*s2="ok

从 1 到 2018 这 2018 个数中，共有___

输入 :8 4输出：____

输入：2 3 4输出：____

输入： CBBADADA输出： ______

LZW 编码是一种自适应词典编码。在编码的过程中，开始

以下逻辑表达式的值恒为真的是（）

输入: 3 1 2输出: __________

在下列各种排序算法中，不是以“比较”作为主要操作的算法

更多选择题

更多填空题

题量:	0 道
总分:	分

（最大公约数之和）下列程序想要求解整数 n的所有约数两

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷

训练

（最大公约数之和）下列程序想要求解整数 n的所有约数两

自由练习

模拟考试

我的成绩

试卷信息

推荐试卷