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

    solution

    Đề bài: [Toán cho CNTT] Cấp của phần tử modulo n

    Cấp (order) của phần tử

    Cho aaa và nnn với gcd⁡(a,n)=1\gcd(a,n)=1gcd(a,n)=1. Cấp của aaa modulo nnn là số nguyên dương nhỏ nhất kkk thỏa: ak≡1(modn).a^{k} \equiv 1 \pmod n.ak≡1(modn).

    Cấp luôn là ước của φ(n)\varphi(n)φ(n). Nếu gcd⁡(a,n)≠1\gcd(a,n)\ne1gcd(a,n)=1, cấp không tồn tại, in -1.

    Ví dụ

    Cấp của 222 modulo 777 là 333 vì 23=8≡1(mod7)2^3 = 8 \equiv 1 \pmod 723=8≡1(mod7).

    • Định dạng đầu vào:

      Một dòng gồm hai số nguyên dương aaa và nnn.

    • Ràng buộc đầu vào:

      1≤a≤1091 \le a \le 10^{9}1≤a≤109, 2≤n≤1092 \le n \le 10^{9}2≤n≤109.

    • Định dạng đầu ra:

      Cấp của aaa mod nnn, hoặc -1 nếu không tồn tại.

    Ví dụ:

    Đầu vào:

    2 7

    Đầu ra:

    3

    Giải thích:

    2^3=8≡1 (mod 7), va khong co mu nho hon.

    Đang tải editor...