Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [An toàn thông tin] Điểm đối trên đường cong Elliptic

    Trên đường cong elliptic E:y2≡x3+ax+b(modp)E: y^2\equiv x^3+ax+b \pmod pE:y2≡x3+ax+b(modp), với mỗi điểm P=(x,y)∈EP=(x,y)\in EP=(x,y)∈E, điểm đối (nghịch đảo cộng) −P-P−P được định nghĩa sao cho P+(−P)=OP+(-P)=OP+(−P)=O (điểm vô cực). Có thể chứng minh −P=(x, p−y mod p)-P=(x,\,p-y \bmod p)−P=(x,p−ymodp); đặc biệt nếu y=0y=0y=0 thì −P=P-P=P−P=P. Quy ước −O=O-O=O−O=O.

    Cho TTT điểm, hãy in ra điểm đối tương ứng của mỗi điểm.

    Ví dụ: với p=97,a=2,b=3p=97,a=2,b=3p=97,a=2,b=3, điểm P=(3,6)P=(3,6)P=(3,6) có −P=(3,97−6)=(3,91)-P=(3, 97-6)=(3,91)−P=(3,97−6)=(3,91).

    • Định dạng đầu vào:
      • Dòng 1: ba số nguyên p a bp\ a\ bp a b.
      • Dòng 2: số nguyên TTT (1≤T≤10001\le T\le 10001≤T≤1000).
      • TTT dòng tiếp theo, mỗi dòng "x yx\ yx y" (điểm đảm bảo thuộc EEE) hoặc "O".
    • Định dạng đầu ra:

      TTT dòng, mỗi dòng in tọa độ điểm đối dạng "x y", hoặc "O" nếu là điểm vô cực.

    Ví dụ:

    Đầu vào:

    97 2 3
4
3 6
30 0
O
1 43

    Đầu ra:

    3 91
30 0
O
1 54

    Đầu vào:

    97 2 3
1
0 10

    Đầu ra:

    0 87

    Đang tải editor...