GESP C++ Level 5 Exam Questions (Number Theory Focus) luogu-P13014 [GESP202506 Level] Greatest Common Divisor

**GESP Learning Resource List**
Exam Questions	Practice Questions	Syllabus Analysis
Level 1 Exam Questions List	Level 1 Practice Questions List	Level 1-5 Syllabus Analysis
Level 2 Exam Questions List	Level 2 Practice Questions List	Essential Skills for GESP/CSP Programming
Level 3 Exam Questions List	Level 3 Practice Questions List
Level 4 Exam Questions List	Level 4 Practice Questions List
Level 5 Exam Questions List	Level 5 Practice Questions List

**CSP Learning Resource List**
CSP-XL
2025 Liaoning CSP-XL Re-examination Questions Analysis

GESP C++ Level 5 exam questions from June 2025, focusing on number theory, with a pruning approach. The difficulty level is ⭐⭐★☆☆, relatively easy for level 5. Difficulty level on LuoguGeneral−

luogu-P13014 [GESP202506 Level] Greatest Common Divisor

Problem Requirements

Problem Description

For two positive integers , their greatest common divisor is denoted as . For positive integers , their greatest common divisor is:

Given positive integers and groups of queries. For the group of queries, request the greatest common divisor of , that is, .

Input Format

The first line contains two positive integers , representing the number of given positive integers and the number of query groups.

The second line contains positive integers .

Output Format

Output a total of lines, with the line containing a positive integer representing the greatest common divisor of .

Input/Output Example #1

Input #1

5 3
6 9 12 18 30

Output #1

1
1
3

Input/Output Example #2

Input #2

3 5
31 47 59

Output #2

Notes/Tips

For the test points, it is guaranteed that ,.

For all test points, it is guaranteed that ,,.

Problem Analysis

This problem tests the properties of the greatest common divisor (GCD) in number theory and optimization strategies for specific data ranges.

Core Idea

The problem requires calculating the greatest common divisor of the sequence . According to the properties of the greatest common divisor, the GCD of multiple numbers equals the GCD of the first two numbers and the GCD of the third number, that is, . This means we can linearly traverse the array to find the overall GCD.

Optimization Idea

If we directly calculate for each group of queries, the total time complexity would be . Considering that and can both reach , the total computation would reach level, which would clearly time out.

Observing the data range, we find a key point: ** is very small, ensuring that .** This is a very important hint. Although is large, there are at most 1000 different values in the array. At the same time, the greatest common divisor has a property:. This means that if there are multiple identical numbers, their contribution to the final GCD is the same as one number. For example, .

Algorithm Process

Therefore, we do not need to traverse numbers, we only need to care about which values from appear in the array.

Preprocessing:

Create a marking array (bucket) of size 1005.
Read in numbers. For each number read in, set the corresponding position in the marking array to 1, indicating that the value exists. This step has a complexity of .

Processing Queries:

For each group of queries :
Initialize the current greatest common divisor cur_gcd to -1 (or marked as not started).
Traverse the value range from to .
If the marking array shows that the value exists, calculate cur_gcd = gcd(cur_gcd, j + i). Note to handle the initial state of cur_gcd.
This step has a complexity of .

Complexity Analysis

Time Complexity: Preprocessing . A total of queries, each traversing numbers. The total complexity is approximately . Substituting the data, the computation amount is about level. Since GCD operations are fast, and most may not exist, the actual running efficiency is very high.
Space Complexity: Only a marking array of size 1005 is needed, with a space complexity of .

Example Code

#include &lt;iostream&gt;// The array a is used to mark whether a number exists. The problem guarantees 1 &lt;= ai &lt;= 1000,// so we can use an array of size 1005 to record whether each number has appeared.int a[1005];// Function to calculate the greatest common divisor (GCD)// using the Euclidean algorithm.int gcd(int a, int b) {    if (b == 0) {        return a;    }    return gcd(b, a % b);}int main() {    int n, q;    // Input n (number of digits) and q (number of query groups)    std::cin &gt;&gt; n &gt;&gt; q;    for (int i = 0; i &lt; n; i++) {        int num;        std::cin &gt;&gt; num;        // Mark that the number num has appeared.        // Since gcd(x, x, y) = gcd(x, y), repeated numbers do not affect the result of the greatest common divisor,        // so we only need to record which numbers have appeared, not the number of occurrences.a[num] = 1;    }    // Process each group of queries    // i indicates the current value added to the query, the problem asks for a_j + i    for (int i = 1; i &lt;= q; i++) {        int cur_gcd = -1;  // Used to store the current calculated greatest common divisor        // Traverse all possible values (1 to 1000)        // Because the range of ai is small, we can directly traverse the value range        for (int j = 1; j &lt;= 1000; j++) {            // If the value j exists in the original array            if (a[j] == 1) {                if (cur_gcd == -1) {                    // If it is the first encountered number, directly use it as the current GCD                    cur_gcd = j + i;                } else {                    // Otherwise, calculate the GCD of the current GCD and (j + i)                    // Update cur_gcd                    cur_gcd = gcd(cur_gcd, j + i);                }            }        }        // Output the answer for the current query        std::cout &lt;&lt; cur_gcd &lt;&lt; std::endl;    }    return 0;}

【Recommended】Mobile Version Recommendation:【GESP】C++ Certification Learning Resource Summary

【Recommended】Desktop Version Recommendation: GESP/CSP Exam Material Website:https://wiki.coderli.com/ Dictionary-style resource organization, easy and quick to browse by category.