Module 5

Xem PDF



Tác giả:
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Bạn có 2 số nguyên dương \(A\), \(B\), và \(A\) chia hết cho \(B\). Nhiệm vụ của bạn là tính \((A/B) \mod{10^{18} + 9}\). Không may, bạn vô tình quên đi giá trị của \(A\)\(B\) và chỉ nhớ giá trị của \(a\)\(b\).

Trong đó, \(a \equiv A \pmod{10^{18} + 9}\)\(b \equiv B \pmod{10^{18} + 9}\)

Input

  • Dòng đầu tiên và duy nhất chứa 2 số nguyên dương \(a\), \(b\) \((a,b \leq 10^{18})\)

Output

  • In ra giá trị của \((A/B) \mod{10^{18} + 9}\).

Example

Test 1

Input
2 3 
Output
333333333333333337

Bình luận


  • 1
    minhtuanitk20 3:43 p.m. 30 Tháng 1, 2022

    dùng fermat được ko a


    • 7
      hhoangcpascal 9:36 p.m. 10 Tháng 7, 2020 đã chỉnh sửa

      Modular Multiplicative Inverse hân hạnh tài trợ chương trình này (Do số 1e18 + 9 là số nguyên tố sẵn nên dùng được)

      2 phản hồi