मान लीजिए, एक गेम शो में 2n कमरे हैं जो एक वृत्त में व्यवस्थित हैं। कमरों में से एक में एक पुरस्कार है जिसे प्रतिभागियों को इकट्ठा करना है। कमरे 1, 2, 3, ..., n, -n, -(n-1), ..., -1 से दक्षिणावर्त क्रम में नंबर किए गए हैं। प्रत्येक कमरे में एक दरवाजा है और उस दरवाजे से एक अलग कमरे में जाया जा सकता है। हर दरवाजे पर एक मार्किंग x होती है, जिसका मतलब है कि दूसरा कमरा वर्तमान कमरे से x दूरी पर स्थित है। यदि x का मान धनात्मक है, तो दरवाजा उस कमरे से xवें कमरे को दक्षिणावर्त दिशा में खोलता है। यदि x का मान ऋणात्मक है, तो इसका मतलब है कि कमरा वामावर्त दिशा में xवें कमरे को खोलता है। हमें उन कमरों की संख्या ढूंढनी है जिनमें पुरस्कार रखा जा सकता है और प्रतिभागियों को पुरस्कार खोजने में कठिनाई होती है।
इसलिए, यदि इनपुट है: input_array = [[4, 2]], तो आउटपुट [2] होगा।
इनपुट में दो मान हैं, पहला मान n है जो कमरों की संख्या का आधा है, और दूसरा मान वह कमरा नंबर है जहां से प्रतिभागी पुरस्कार ढूंढना शुरू करते हैं। यहां 2×4 = 8 कमरे हैं और प्रतिभागी दक्षिणावर्त दिशा में दूसरे कमरे से पुरस्कार ढूंढना शुरू करते हैं। कमरे दक्षिणावर्त क्रम में इस तरह नंबर किए गए हैं: 1, 2, 3, 4, -4, -3, -2, -1। प्रतिभागी इस तरीके से कमरों में जाएंगे: 2, -4, -1, 1, 3, -2, -1, 1, 3, -2, ... तो कमरे 4 और -3 कभी विजिट नहीं होते, यदि पुरस्कार इन दो कमरों में से किसी में छिपा है तो प्रतिभागी इसे नहीं ढूंढ सकते।
हल करने के चरण
- prime_num_find() फंक्शन परिभाषित करें जो n लेता है
- factor_finder() फंक्शन परिभाषित करें जो p लेता है
- euler_func() फंक्शन परिभाषित करें जो p लेता है
- मुख्य फंक्शन से:
- output := नई सूची
- input_array में प्रत्येक item के लिए:
- p := item[0], q := item[1]
- r := 2 * p + 1
- r := floor(r / gcd(r, q % r))
- t_value := euler_func(r)
- factor_finder(t_value) में प्रत्येक value के लिए:
- जब t_value % value == 0 और (2^(t_value/value) mod r) == 1: t_value //= value
- output के अंत में 2 * p - t_value डालें
- output वापस करें
उदाहरण
import math
def prime_num_find(n):
p_nums = [2]
check = bytearray(n)
for value in range(3, n, 2):
if check[value]:
continue
p_nums.append(value)
for i in range(3 * value, n, 2 * value):
check[i] = 1
return p_nums
def factor_finder(p):
p_nums = prime_num_find(45000)
f_nums = {}
for value in p_nums:
if value * value > p:
break
while p % value == 0:
p //= value
f_nums[value] = f_nums.get(value, 0) + 1
if p > 1:
f_nums[p] = 1
return f_nums
def euler_func(p):
f_nums = factor_finder(p)
t_value = 1
for value in f_nums:
t_value *= (value - 1) * value ** (f_nums[value] - 1)
return t_value
def solve(input_array):
output = []
for item in input_array:
p, q = item[0], item[1]
r = 2 * p + 1
r //= math.gcd(r, q % r)
t_value = euler_func(r)
for value in factor_finder(t_value):
while t_value % value == 0 and pow(2, t_value // value, r) == 1:
t_value //= value
output.append(2 * p - t_value)
return output
print(solve([[4, 2]]))
इनपुट
[[4, 2]]
आउटपुट
[2]
