結果

問題 No.1999 Lattice Teleportation
コンテスト
ユーザー MasKoaTS
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0