結果
| 問題 |
No.1274 楽しい格子点
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:05:00 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 120 ms / 2,000 ms |
| コード長 | 5,816 bytes |
| コンパイル時間 | 156 ms |
| コンパイル使用メモリ | 82,660 KB |
| 実行使用メモリ | 80,780 KB |
| 最終ジャッジ日時 | 2025-05-14 13:06:43 |
| 合計ジャッジ時間 | 7,497 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 57 |
ソースコード
# Import necessary libraries
import sys
import math
# Use Decimal for high precision floating point arithmetic
from decimal import Decimal, getcontext
# Set the precision for Decimal operations.
# 60 digits should be more than sufficient for the required error tolerance of 10^-6.
getcontext().prec = 60
def solve():
# Read the integer inputs A and B from standard input
A, B = map(int, sys.stdin.readline().split())
# Handle the trivial case where A=0 and B=0.
# In this case, the only allowed move is (p+0, q+0), so we stay at the starting point (1,1).
# The value at (1,1) is 1/(1+1)^(1+1) = 1/2^2 = 1/4.
if A == 0 and B == 0:
# Print the result as a Decimal
print(Decimal(1) / Decimal(4))
return
# Calculate G = gcd(|A|, |B|).
# Need special handling if A or B is 0 because math.gcd requires non-negative arguments
# and gcd(x, 0) = |x|.
if A == 0:
# If A is 0, GCD is |B|
G = abs(B)
elif B == 0:
# If B is 0, GCD is |A|
G = abs(A)
else:
# If both A and B are non-zero, use math.gcd on their absolute values
G = math.gcd(abs(A), abs(B))
# Calculate A' = A/G and B' = B/G.
# Ensure integer division using `//`. A', B' are coprime integers.
A_prime = A // G
B_prime = B // G
# Initialize the total sum as a Decimal
total_sum = Decimal(0)
# The set of reachable points (x, y) from (1, 1) are those where (x-1, y-1)
# belongs to the lattice L generated by the 8 move vectors.
# The structure of this lattice depends on the parity of A' and B'.
# Check the parity condition of A' and B'.
# `A_prime % 2 != B_prime % 2` is True if A' and B' have different parity.
# Python's % operator handles negative numbers correctly for parity checks.
if A_prime % 2 != B_prime % 2:
# Case 1: A' and B' have different parity.
# The lattice L contains all points (X, Y) such that X and Y are multiples of G.
# Reachable points (x, y) satisfy x >= 1, y >= 1, x = 1 (mod G), y = 1 (mod G).
# The sum formula is: sum_{S=0 to inf} (S+1) / (G*S + 2)^(G*S + 2)
S = 0 # Start summing from S=0
while True:
# Calculate the base T = G*S + 2 for the term
term_val_base = Decimal(G * S + 2)
# Calculate the term (S+1) / T^T
try:
# Use Decimal's built-in power method for high precision exponentiation.
term = (Decimal(S+1)) / (term_val_base ** term_val_base)
except Exception as e:
# If any error occurs during calculation (e.g., overflow, invalid operation),
# treat the term as effectively zero. This might happen for extremely large bases/powers,
# although Decimal handles large numbers well.
# Print debugging info if needed: print(f"Exception occurred for S={S}: {e}", file=sys.stderr)
term = Decimal(0)
# Add the calculated term to the total sum
total_sum += term
# Check for convergence. If the term becomes extremely small (e.g., < 1e-40),
# and we are past the first term (S>0), the remaining terms are negligible.
# The threshold 1e-40 is chosen conservatively for precision 60.
if term < Decimal('1e-40') and S > 0:
break
# Safety break: prevent potential infinite loops in unexpected scenarios.
# The series converges very rapidly, so S rarely needs to exceed a small number.
# 100 iterations is significantly more than typically needed.
if S > 100:
# Print debugging info if needed: print(f"Warning: Loop limit S=100 exceeded in different parity case.", file=sys.stderr)
break
# Increment S to compute the next term
S += 1
else:
# Case 2: A' and B' have the same parity.
# Since gcd(A', B') = 1, they must both be odd.
# The lattice L contains points (X, Y) such that X, Y are multiples of G, and X/G = Y/G (mod 2).
# Reachable points (x,y) satisfy x >= 1, y >= 1, x = 1 (mod G), y = 1 (mod G), and (x-1)/G = (y-1)/G (mod 2).
# The sum formula is: sum_{S=0, S even to inf} (S+1) / (G*S + 2)^(G*S + 2)
S = 0 # Start summing from S=0
while True:
# Only calculate terms for even values of S
if S % 2 == 0:
# Calculate base T = G*S + 2
term_val_base = Decimal(G * S + 2)
# Calculate the term (S+1) / T^T
try:
term = (Decimal(S+1)) / (term_val_base ** term_val_base)
except Exception as e:
# Handle potential exceptions during calculation
# print(f"Exception occurred for S={S}: {e}", file=sys.stderr)
term = Decimal(0)
# Add term to sum
total_sum += term
# Check convergence for the current even S term
if term < Decimal('1e-40') and S > 0:
break
# Safety break based on S regardless of parity check
if S > 100:
# Print debugging info if needed: print(f"Warning: Loop limit S=100 exceeded in same parity case.", file=sys.stderr)
break
# Increment S to check the next potential term value
S += 1
# Print the final computed sum. Using standard print with Decimal type
# will output the number with the precision set by `getcontext().prec`.
print(total_sum)
# Execute the solve function
solve()