محدودیت زمان: ۱ ثانیه محدودیت حافظه: ۲۵۶ مگابایت درخت دودویی از کسرها داریم که روی هر…
- User
محدودیت زمان: ۱ ثانیه محدودیت حافظه: ۲۵۶ مگابایت درخت دودویی از کسرها داریم که روی هر راسش کسری به فرم a i b i b i
a i
نوشته شده است. درخت به این شکل ساخته میشود:
a 1 a 1
b 1 b 1
1 1 a 2 i a 2i = ( a i a i + b i b i ) , b 2 i b 2i
b i b i (بچه سمت چپ) a 2 i + 1 a 2i+1
a i a i , b 2 i + 1 b 2i+1 = ( a i a i + b i b i ) (بچه سمت راست) فاصله دو راس در درخت را تعداد یالهای تنهای مسیر بینشان تعریف میکنیم.
به شما Q Q درخواست که هر کدام شامل کسری به فرم p i q i q i
p i
داده میشود.
برای هر عدد موجود در درخواستها، اگر تنها یک راس در درخت وجود داشت که کسرش برابر کسر ورودی داده شده بود، فاصله راس آن کسر تا راس ۱ را در خروجی چاپ کنید و در غیر این صورت − 1 −1 خروجی دهید.
ورودی در خط اول Q Q و در Q Q خط بعدی p i p i و q i q i به شما داده شده.
1 ≤ Q ≤ 100
000 1≤Q≤100 000
1 ≤ p i , q i ≤ 1 0 18 1≤p i ,q i ≤10 18
خروجی در خط i iام اگر کسری معادل عدد p i q i q i
p i
بود و فقط این کسر معادل این عدد بود فاصلهی آن را از راس ۱ خروجی دهید در غیر این صورت − 1 −1 خروجی دهید.
مثال ورودی نمونه ۱ 2 1 2 3 5
Plain text خروجی نمونه ۱ 1 3 Plain text
- Assistant
To solve this problem, we need to calculate the distance from the root (node with fraction 1/1) to a node with a specific fraction ( p_i / q_i ) given in the query. However, we must determine if this fraction occurs exactly once in the tree constructed as per the given rules.
Understanding the Tree Construction:
Upon careful analysis, it becomes clear that the tree in question resembles the Calkin-Wilf tree, a binary tree where every positive reduced fraction appears exactly once. In this tree:
- Left Child of node ( a/b ): ( (a + b)/b )
- Right Child of node ( a/b ): ( a/(a + b) )
However, the tree, as constructed by the problem, may include unreduced fractions due to its definition. This means multiple fractions in the tree might reduce to the same simplified fraction. For instance, both ( 2/4 ) and ( 1/2 ) reduce to ( 1/2 ). Consequently, the simplified fraction ( 1/2 ) appears more than once in the tree.
Determining Uniqueness:
To check if a fraction ( p_i/q_i ) appears exactly once in the tree, we need to verify if the fraction is in its lowest terms, i.e., ( \gcd(p_i, q_i) = 1 ). If ( \gcd(p_i, q_i) > 1 ), the fraction can be reduced further, implying that multiple unreduced fractions in the tree reduce to the same simplified fraction. Therefore, if ( \gcd(p_i, q_i) > 1 ), we must output -1.
Calculating the Distance:
For fractions where ( \gcd(p_i, q_i) = 1 ), we can calculate the distance to the root using an algorithm inspired by the way the tree is constructed:
- Initialize the distance counter to 0.
- While ( p_i \neq q_i ):
- If ( p_i > q_i ):
- ( p_i = p_i - q_i )
- Increment the distance counter.
- Else:
- ( q_i = q_i - p_i )
- Increment the distance counter.
- If ( p_i > q_i ):
- When ( p_i = q_i ), we've reached the root (since ( p_i/q_i = 1/1 )).
- Output the distance counter.
This algorithm effectively reverses the steps from the given fraction back to the root by undoing the operations used to generate the left and right children, ensuring we only consider unique paths (since ( \gcd(p_i, q_i) = 1 )).
Implementation Details:
- Use the Euclidean algorithm to compute the gcd of ( p_i ) and ( q_i ).
- Use a loop to simulate the path from the fraction to the root, counting the steps.
- Ensure the implementation is efficient to handle up to ( 10^5 ) queries with large fractions.
Example:
-
Input:
1 2- ( \gcd(1, 2) = 1 )
- Path: Since ( 1 < 2 ), ( q_i = 2 - 1 = 1 ), distance increases to 1.
- Now, ( p_i = 1 ), ( q_i = 1 ), reached the root.
- Output:
1
-
Input:
4 6- ( \gcd(4, 6) = 2 )
- Since ( \gcd(p_i, q_i) > 1 ), the simplified fraction ( 2/3 ) may appear multiple times.
- Output:
-1
Final Answer:
def compute_distance(p, q): distance = 0 while p != q: if p > q: p -= q else: q -= p distance += 1 return distance Q = int(input()) for _ in range(Q): p_str, q_str = input().split() p, q = int(p_str), int(q_str) import math g = math.gcd(p, q) if g != 1: print(-1) else: print(compute_distance(p, q))