You are viewing a single comment's thread. Return to all comments →
This solution with python , but has some test faild because of Time limit exceeded .
Seems like cookies are disabled on this browser, please enable them to open this website
Primitive Problem
You are viewing a single comment's thread. Return to all comments →
This solution with python , but has some test faild because of Time limit exceeded .
import math
import os
import random
import re
import sys
def power(x, y, p):
result = 1
x = x % p
while y > 0:
if y & 1:
result = (result * x) % p
y = y >> 1
x = (x * x) % p
return result
def is_primitive_root(g, p, factors):
for factor in factors:
if power(g, (p - 1) // factor, p) == 1:
return False
return True
def find_primitive_roots(p):
primitive_roots = []
factors = set()
# Find prime factors of p-1
for i in range(2, int(math.sqrt(p-1)) + 1):
if (p - 1) % i == 0:
factors.add(i)
factors.add((p - 1) // i)
for g in range(2, p):
if is_primitive_root(g, p, factors):
primitive_roots.append(g)
return primitive_roots
def smallest_primitive_root(p):
primitive_roots = find_primitive_roots(p)
return min(primitive_roots)
if name == 'main':
p = int(input().strip())
smallest_root = smallest_primitive_root(p)
total_roots = len(find_primitive_roots(p))
print(smallest_root, total_roots)