We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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
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)
def smallest_primitive_root(p): primitive_roots = find_primitive_roots(p) return min(primitive_roots)
if name == 'main': p = int(input().strip())