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

    solution

    Đề bài: [Toán rời rạc] Hàm Möbius của poset chia hết

    Trong poset chia hết với phần tử nhỏ nhất là 1, hàm Möbius μ(1,n)\mu(1,n)μ(1,n) trùng với hàm Möbius số học: μ(1)=1\mu(1)=1μ(1)=1; μ(n)=0\mu(n)=0μ(n)=0 nếu nnn chia hết cho một bình phương >1>1>1; ngược lại μ(n)=(−1)r\mu(n)=(-1)^rμ(n)=(−1)r với rrr là số ước nguyên tố phân biệt của nnn. Cho nnn, in μ(1,n)\mu(1,n)μ(1,n).

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

      Một dòng chứa số nguyên nnn.

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

      1≤n≤10121 \le n \le 10^{12}1≤n≤1012.

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

      Một dòng: μ(1,n)∈{−1,0,1}\mu(1,n)\in\{-1,0,1\}μ(1,n)∈{−1,0,1}.

    Ví dụ:

    Đầu vào:

    6

    Đầu ra:

    1

    Giải thích:

    $6=2\cdot 3$ không có thừa số bình phương, 2 ước nguyên tố nên $\mu=(-1)^2=1$.

    Đang tải editor...