একটি হাইপাররেক্ট্যাঙ্গেলের k ডাইমেনশন আছে, প্রতিটি ডাইমেনশনের দৈর্ঘ্য n1, n2, ..., nm। সেলগুলো এড্রেস করা হয় (p,q,r,...) এবং মান থাকে gcd(p,q,r,...)। ১ ≤ p ≤ n1, ১ ≤ q ≤ n2, ইত্যাদি। সব সেলের gcd যোগফল বের করতে হবে (মডুলো ১০⁹+৭)। ইন্ডেক্সিং ১ থেকে শুরু।
ইনপুট: [[2,2], [5,5]] → আউটপুট: [5, 37]।
প্রথম ইনস্ট্যান্স (২×২): gcd যোগফল = ১+১+১+২ = ৫।
দ্বিতীয় ইনস্ট্যান্স (৫×৫): gcd যোগফল = ৩৭।
সমাধানের ধাপসমূহ (ইনক্লুশন-এক্সক্লুশন + মবিয়াস ইনভার্সন)
coeff_find(test_instance, i): ∏(k // i) for k in test_instance
প্রতিটি test_instance-এর জন্য:
- min_value = min(test_instance)
- total_value = 0, temp_dict = {}
- i = min_value থেকে ১ পর্যন্ত (উল্টা):
- p = coeff_find(test_instance, i)
- q = i; যখন q <= min_value: q += i; যদি q ∈ temp_dict: p -= temp_dict[q]
- temp_dict[i] = p
- total_value += temp_dict[i] * i
total_value % (10⁹+7) আউটপুটে যোগ করুন
উদাহরণ (Python)
def coeff_find(test_instance, i):
value = 1
for k in test_instance:
value *= k // i
return value
def solve(input_arr):
output = []
for test_instance in input_arr:
min_value = min(test_instance)
total_value = 0
temp_dict = {}
for i in range(min_value, 0, -1):
p = coeff_find(test_instance, i)
q = i
while q <= min_value:
q += i
if q in temp_dict:
p -= temp_dict[q]
temp_dict[i] = p
total_value += temp_dict[i] * i
output.append(total_value % (10**9 + 7))
return output
print(solve([[2, 2], [5, 5]]))
ইনপুট
[[2, 2], [5, 5]]
আউটপুট
[5, 37]
