Cows and Primitive Roots · Interview Problem

Back to problems

Codeforces

Medium

Number Theory

Math

Sorting

Cows and Primitive Roots

Count integers in a range that are primitive roots modulo a given prime.

Acceptance 0%

Start Practice

Also Available On

Other platform versions and source mappings for the same problem.

Codeforces 284A

gfg

Problem Statement

Problem

You are given a prime number $p$ and a range of integers. Your task is to count how many integers in the range are primitive roots modulo $p$ .

An integer $g$ is called a primitive root modulo $p$ if its powers generate all non-zero residues modulo $p$ .

In other words, the values $g^1 \bmod p,\ g^2 \bmod p,\ \dots,\ g^{p-1} \bmod p$ contain every number from $1 $to$ p-1$ exactly once.

Return the count of numbers in the given interval that satisfy this property.

Input Format

A prime integer $p$
A range of integers $[l, r]$

The exact input format is the standard one used by the platform.

Output Format

Output a single integer — the number of primitive roots modulo $p$ that lie in the given range.

Constraints

$p$ is prime
The range bounds are integers
A number can only be a primitive root modulo $p$ if it is coprime to $p$

The exact official limits are not provided in the source metadata.

Examples

Sample cases returned by the problem API.

Example 1

Input

p = 7
l = 1
r = 6

Output

Explanation

The primitive roots modulo 7 are 3 and 5, so there are 2 numbers in the range [1, 6].

Example 2

Input

p = 11
l = 1
r = 10

Output

Explanation

The primitive roots modulo 11 are 2, 6, 7, and 8.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress