GESP Level 5 Practice, Recursion and Greatest Common Divisor, DifficultyGeneral Group.

• CCF-GESP C++ Assessment Standards

  Hongyang, WeChat Official Account: Hongyang’s Programming Class CCF-GESP C++ Assessment Standards

Comprehensive Guide – [GESP2506 Level 5] Greatest Common Divisor

Problem Requirements

Problem Description

For two positive integers a, b, their greatest common divisor is denoted as gcd(a, b).For k ≥ 3 positive integers c1, c2, …, ck, their greatest common divisor is:gcd(c1, c2, …, ck) = gcd(gcd(c1, c2, …, ck – 1), ck)

Given n positive integers a1, a2, …, an and q groups of queries.For the i-th (1 ≤ i ≤ q) group of queries, request the greatest common divisor of a1 + i, a2 + i, …, an + i, that is gcd(a1 + i, a2 + i, …, an + i).

Input Format

The first line contains two positive integers n, q, representing the number of given positive integers and the number of query groups.The second line containsn positive integers a1, a2, …, an..

Output Format

The output consists of q lines, where the i th line contains a positive integer representing the greatest common divisor of a1 + i, a2 + i, …, an + i.

Input and Output Examples

Input #1

5 3

6 9 12 18 30

Output #1

1

1

3

Input #2

3 5

31 47 59

Output #2

4

1

2

1

4

Data Range

For 60% of the test cases, ensure 1 ≤ n ≤ 10³, 1 ≤ q ≤ 10. For all test cases, ensure 1 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10⁵, 1 ≤ ai ≤ 1000.

Problem Analysis

Solution Approach 1 (Brute Force, 60 points)

• For each query <span>i</span>, start from the first number <span>num[1] + i</span>.

• Sequentially calculate the greatest common divisor with each subsequent number <span>num[j] + i</span>.

• Use the recursive Euclidean algorithm to calculate the gcd of two numbers.

• Finally obtain the greatest common divisor of all n numbers.

Algorithm Characteristics:

• The approach is straightforward and easy to understand.

• However, it requires traversing all n numbers for each query.

• Efficiency is low when n and q are large.

Complexity Analysis:

• Time complexity is O(q × n × log(max_value))

• Space complexity is O(n)

Example Code

#include <bits/stdc++.h>using namespace std;// Calculate the greatest common divisor of two numbers (recursive implementation)int gcd(int a, int b){    return b == 0 ? a : gcd(b, a % b);}int n, q;int num[100005]; // Store the input n positive integersint main(){    scanf("%d%d", &n, &q);    for(int i = 1; i <= n; i++) scanf("%d", &num[i]);        for(int i = 1; i <= q; i++){// Process q queries        // Initialize answer as the first number plus the current query value        int ans = num[1] + i;                // Traverse subsequent numbers, calculating gcd with the current answer        for(int j = 2; j <= n; j++){            ans = gcd(ans, num[j] + i);        }                printf("%d\n", ans);// Output the result of the current query    }        return 0;}

Solution Approach 2 (Optimized Mathematical Formula)

The greatest common divisor has an important property:<span>gcd(x, y) = gcd(x, y - x)</span>, which can be generalized to multiple numbers:

<span>gcd(x, y, z) = gcd(x, gcd(y - x, z - x))</span>

Using this property, we can transform the original expression:

gcd(a₁ + i, a₂ + i, ⋯, aₙ + i)= gcd(a₁ + i, (a₂ + i) - (a₁ + i), (a₃ + i) - (a₁ + i), …, (aₙ + i) - (a₁ + i))= gcd(a₁ + i, a₂ - a₁, a₃ - a₁, …, aₙ - a₁)= gcd(a₁ + i, gcd(a₂ - a₁, a₃ - a₁, …, aₙ - a₁))

That is: gcd(a2 – a1, a3 – a1, …, an – a1) can be calculated in advance, denoted as g, and then we only need to calculate gcd(a1 + i, g) for the result. Finally, we compute the greatest common divisor with a1 + i.

Complexity Analysis:

• Time complexity is O(n)

• Space complexity is O(n)

Example Code

#include <bits/stdc++.h>using namespace std;int gcd(int a, int b){    return b==0 ? a : gcd(b,a%b);}int n, q;int num[100005];int main(){    scanf("%d%d", &n, &q);        // Read all numbers    for(int i = 1; i <= n; i++){        scanf("%d", &num[i]);    }        // Calculate the gcd of all differences (excluding the first number with itself)    int g = 0;    for(int i = 2; i <= n; i++){        g = gcd(g, abs(num[i] - num[1]));    }        // For each query, calculate gcd(num[1]+i, g)    for(int i = 1; i <= q; i++){        printf("%d\n", gcd(num[1] + i, g));    }        return 0;}

“Comprehensive Guide–” series problems can be evaluated online atInformatics Olympiad Comprehensive Guide (C++ Version).