GESP C++ Level 5 Exam Questions (Number Theory Focus) luogu-P11961 [GESP202503 Level 5] Primitive Root Determination

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

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

GESP C++ Level 5 actual questions from March 2025, focusing on number theory, may exceed the syllabus scope, with a difficulty rating of ⭐⭐⭐★☆, quite challenging for level 5. LuoGu difficulty levelIncrease+/Provincial Selection−

luogu-P11961 [GESP202503 Level 5] Primitive Root Determination

Problem Requirements

Problem Background

As of March 2025, this problem may exceed the GESP syllabus scope. At this point, the concept of primitive roots is a level 8 knowledge point in the NOI syllabus (NOI level), while the relatively simpler methods that do not require knowledge of primitive roots, using Fermat’s Little Theorem and Euler’s Theorem, are also level 7 knowledge points (advanced level), and are not explicitly stated in the GESP syllabus. It is important to note that the GESP syllabus and the NOI syllabus are different.

If you are interested in the concept of primitive roots in this problem, you can study the completed 【Template】 for primitive roots.

Problem Description

Little A knows that for a prime , the primitive root is a positive integer that satisfies the following conditions:

$1$

;

For any 1 ≤ i < p-1, g^i mod p ≠ 1

Where denotes the remainder of divided by .

Little A now has an integer , please help him determine if is a primitive root of .

Input Format

The first line contains a positive integer , indicating the number of test cases.

Each test case contains a line with two positive integers .

Output Format

For each test case, output a line. If is a primitive root of , output Yes, otherwise output No.

Input Output Example #1

Input #1

3
3 998244353
5 998244353
7 998244353

Output #1

Yes
Yes
No

Notes/Tips

Data Range

For the test points of , it is guaranteed that .

For all test points, it is guaranteed that , $1<a<p$, where $p$ is prime.

Problem Analysis

To be honest, I think this problem is quite challenging for GESP level 5 lower grade students, it seems overly difficult. I also took a long time to understand the relevant theorems and provide code examples.

1. Common Understanding: What is a “Primitive Root”?

The problem gives three conditions, let’s translate them. Assume the modulus is a prime (for example, ).

Condition 1: . (This just limits the range of , the input guarantees it, so no need to worry)
Condition 2: . (According to Fermat’s Little Theorem, as long as is prime and is not a multiple of , this condition always holds, so no need for special checks)
Condition 3 (Core): For any , there is .

Common Explanation: You can think of as a generator that generates numbers in the modulus world by continuously multiplying itself ().

The power must return to 1 (this is the endpoint).
However, the primitive root requires this “generator” to traverse the entire journey from to before the last step (the step) can return to 1.
If it returns to 1 early (in the step, where ), then it has “slacked off” and is not a primitive root.

Example (): We need to check if is a primitive root. We need to see to .

👉 Note: Here is already 1.
Since , it returned to 1 early. So 2 is not a primitive root of 7.

Now check :

👉 Only at the last step does it equal 1.
It did not return to 1 early, so 3 is a primitive root of 7.

2. Problem Solving Approach: How to Quickly Determine?

Brute Force Method (Will Time Out)

The most direct idea is to write a loop from to , calculating one by one to see if it equals 1.

If one equals 1, output No.
If none do, output Yes.

Problem: The maximum is . If you loop times, the program will run for several seconds or even time out (the computer can run about times in one second).

Number Theory Optimization Method (Correct Solution)

We need to use a mathematical conclusion: If returns to 1 “early”, then the number of steps (exponent) it takes to return to 1 must be a divisor of .

Furthermore, through derivation, we can derive the sufficient and necessary condition for determining primitive roots: For each prime factor of , if all satisfy:

Then is a primitive root.

As long as there is one prime factor such that , then is not a primitive root.

Thus, the algorithm steps become simple.

3. Algorithm Steps

To determine if is a primitive root of , we need to do three things:

Calculate .
Perform prime factorization of .

Find all distinct prime factors of .
For example: If , then , the prime factors are 2 and 3.
For example: If , then , the only prime factor is 2.

Perform fast power detection.(This part of the algorithm will be detailed later, commonly used algorithm)

For each prime factor , calculate .
If a certain is found, it indicates that it has returned to 1 “early”, determination fails (No).
If all prime factors are tested and none return 1, determination succeeds (Yes).

Example Code

#include <algorithm>
#include <iostream>
#include <vector>
// Fast power modulo function
// Calculate (base^exp) % mod
// Use long long to prevent overflow of intermediate results
long long power_mod(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        // If the exponent is odd, multiply the current base into the result
        if (exp & 1) {
            result = result * base % mod;
        }
        // Base self-multiply, exponent right shift by one (divide by 2)
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}
int main() {
    // Optimize I/O operations
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T;
    std::cin >> T;
    while (T--) {
        int a, p;
        std::cin >> a >> p;
        // Condition 1: 1 < a < p, the problem data naturally satisfies
        // Condition 2: Fermat's Little Theorem: if p is prime, then a^(p-1) mod p = 1
        // Always holds, the problem guarantees p is prime, naturally satisfied, no extra judgment needed.
        // Equivalent determination of Condition 3:
        // For any prime factor q of p-1, if a^((p-1)/q) mod p == 1, then a is not a primitive root.
        // This method is more efficient than enumerating all 1 <= i < p-1.
        int target = p - 1;
        std::vector<int> primes;
        // Factor prime factors: find all distinct prime factors of p-1
        for (int i = 2; i * i <= target; i++) {
            if (target % i == 0) {
                primes.push_back(i);
                // Completely divide out the current prime factor i
                while (target % i == 0) {
                    target /= i;
                }
            }
        }
        // If target > 1, it means the remaining target itself is a prime factor
        if (target > 1) {
            primes.push_back(target);
        }
        bool flag = true;
        // Iterate through all prime factors q of p-1
        for (int q : primes) {
            // Calculate exponent (p-1)/q
            int tmp = (p - 1) / q;
            // Check if a^((p-1)/q) % p equals 1
            // If equal to 1, it indicates that there exists a smaller exponent that satisfies the congruence 1, violating the definition of primitive root
            if (power_mod(a, tmp, p) == 1) {
                flag = false;
                break;
            }
        }
        if (flag) {
            std::cout << "Yes\n";
        } else {
            std::cout << "No\n";
        }
    }
    return 0;
}

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

【Recommended】Desktop Version Recommended: GESP/CSP Exam Material Website:https://wiki.coderli.com/ Dictionary-style resource organization, categorized for easy and quick access.