#A. 图灵初赛练习5(普及组)

    客观题

图灵初赛练习5(普及组)

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

阅读程序(12分)

1	#include<iostream>
2	#include<cstring>
3	using namespace std;
4	const int mm = 1007;
5	int map[mm][mm];
6	int n;
7	int main() {
8		cin>>n;
9		n--;
10		memset(map,0,sizeof(map));
11		for(int i=0;i<n;i++) {
12			for(int j=0;j<n;j++) {
13				map[i][j]=(i+j)%n+1;
14			}
15		}
16		for(int i=0;i<n;i++) {
17			map[i][n]=map[n][i]=map[i][i];
18			map[i][i]=0;
19		}
20		for(int i=0;i<=n;i++) {
21			for(int j=0;j<=n;j++) {
22				cout<<map[i][j]<<" ";
23			}
24			cout<<endl;
25		}
26	}

规定:输入的 nn 为偶数

判断题

  1. n=6n=6map[3][6]map[3][6] 的值是 44 。(){{ select(1) }}
  • 正确
  • 错误
  1. 若将第 1010 行的 00 改为 1-1,输出结果会发生改变。(){{ select(2) }}
  • 正确
  • 错误
  1. 输出的值形成一个矩阵,且该矩阵关于从左上到右下的对角线对称。() {{ select(3) }}
  • 正确
  • 错误
  1. 值为 xx 的位置有 (i1,j1),(i2,j2),(i_1,j_1),(i_2,j_2),\dots ,则任意两个位置的 iijj 都不相同() {{ select(4) }}
  • 正确
  • 错误

选择题

  1. n=8n=8 时,输出的第 44 行的值的和是()。{{ select(5) }}
  • 28
  • 36
  • 8
  • 7
  1. 输出的从右上到左下对角线的值的和是。{{ select(6) }}
  • 0
  • n
  • n*(n-1)/2
  • (n+1)*n/2

完善程序(15分)

下列程序想要求解整数 nn 的所有约数两两之间最大公约数的和对 1000710007 求余后的值,试补全程序。

举例来说,44 的所有约数是 1,2,41,2,41122 的最大公约数为 112244 的最大公约数为 221144 的最大公约数为 11 ,于是答案为 1+2+1=41+2+1=4

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

1	#include <iostream>
2	using namespace std;
3	
4	const int N = 110000, P = 10007;
5	int n;
6	int a[N], len;
7	int ans;
8	
9	void getDivisor() {
10	    len = 0;
11	    for (int i = 1; ① ; ++i)
12	        if (n % i == 0) {
13	          a[++len] = i;
14	          if ( ② ) a[++len] = n / i;
15	        }
16	}
17	
18	int gcd(int a, int b) {
19	    if (b == 0) {
20	    	③ ;
21	    }
22	    return gcd(b, ④ );
23	}
24	
25	int main() {
26	    cin >> n;
27	    getDivisor();
28	    ans = 0;
29	    for (int i = 1; i <= len; ++i) {
30	        for (int j = i + 1; j <= len; ++j) {
31	        	ans =  ⑤ ;
32	        }
33	    }
34	    cout << ans << endl;
35	    return 0;
36	}
  1. ① 处应填( ){{ select(7) }}
  • i < n
  • i <= n
  • i * i <= n
  • i < sqrt(n)
  1. ② 处应填( ){{ select(8) }}
  • i * i <= n
  • i != n
  • n / i == i
  • n / i != i
  1. ③ 处应填( ){{ select(9) }}
  • return a
  • return b
  • return a % b
  • return b % a
  1. ④ 处应填( ){{ select(10) }}
  • b / a
  • a / b
  • b % a
  • a % b
  1. ⑤ 处应填( ){{ select(11) }}
  • gcd(a[i], a[j])
  • gcd(a[i], a[j]) % P
  • ans + gcd(a[i], a[j]) % P
  • ans + gcd(a[i], a[j])

2024年7月26日 初赛练习(5)【普及组】

未参加
状态
已结束
规则
OI
题目
1
开始于
2024-7-26 17:00
结束于
2024-7-29 0:00
持续时间
0.7 小时
主持人
参赛人数
51