結果
問題 |
No.1999 Lattice Teleportation
|
ユーザー |
![]() |
提出日時 | 2024-12-02 15:11:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 931 ms / 2,000 ms |
コード長 | 1,385 bytes |
コンパイル時間 | 333 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 90,332 KB |
最終ジャッジ日時 | 2024-12-02 15:11:40 |
合計ジャッジ時間 | 14,182 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
import sys from math import gcd input = sys.stdin.readline MOD = 10 ** 9 + 7 class Vector2: def __init__(self, x: int, y: int): self.x = x self.y = y def __lt__(self, other): return area(self, other) > 0 def area(v1: Vector2, v2: Vector2) -> int: return v1.x * v2.y - v1.y * v2.x def floor_sum(n, m, a, b): if(m == 0): return 0 ret = 0 while(True): if(a >= m or a < 0): ret += n * (n - 1) * (a // m) // 2 a %= m if(b >= m or b < 0): ret += n * (b // m) b %= m y_max = a * n + b if(y_max < m): break n, b, m, a = y_max // m, y_max % m, a, m return ret n = int(input()) vectors = [] for _ in [0] * n: x, y = map(int, input().split()) if(x == 0 and y == 0): continue if(y < 0): x, y = -x, -y vectors.append(Vector2(x, y)) vectors.sort() ans = 1 for v in vectors: ans += gcd(v.x, v.y) ans %= MOD def count(): global ans, last, x a, s = k, 0 if(x < 0): a, x = -a, -x s += floor_sum(x, x, y, 0) % MOD + x * last % MOD s %= MOD ans += MOD + a * s ans %= MOD last += MOD + y last %= MOD last, k = 0, 1 for v in vectors[::-1]: x, y = v.x, v.y count() last, k = 0, -1 for v in vectors: x, y = v.x, v.y count() print(ans)