Phân số tối giản(LQD'19)

View as PDF
Submit solution
Points: 1400 (partial)
Time limit: 1.0s
Memory limit: 64M
Input: stdin
Output: stdout
Author:
Small
Problem types

Một phân số được gọi là phân số tối giản nếu ước chung lớn nhất của tử số và mẫu số bằng 1.

Yêu cầu: Cho trước một số nguyên dương N. Hãy đếm xem có bao nhiêu phân số dương bé hơn 1, có mẫu là N và là phân số tối giản.

Input

  • Chứa một số nguyên dương N (N ≤ 10^{16}).

Ouput

  • Ghi ra số nguyên M là số lượng phân số theo yêu cầu trên

Example

Test 1

Input 
9
Output 
6
Note

Có 6 phân số dương bé hơn 1 có mẫu bằng 9 và là phân số tối giản là \frac{1}{9};\frac{2}{9};\frac{4}{9};\frac{5}{9};\frac{7}{9};\frac{8}{9}

Nguồn: TS10LQD 2019

Comments


  • 0
    canhnam357  commented on 10:54 p.m. 12 jan, 2022 ← edited

    Duyệt trâu pass :v


  • 0
    huyhau6a2  commented on 5:53 p.m. 24 dec, 2021

    mình nghĩ dùng bao hàm loại trừ mà sao không ac nhờ(trên 90 test rồi, còn mấy test vặt và test cuối thôi)


  • 0
    Lê_Gia_Khánh  commented on 8:35 p.m. 27 jun, 2020

    Dùng thuật toán Miller


    • 0
      minhtuanitk20  commented on 9:07 p.m. 30 oct, 2021

      sài phi hàm euler kết hợp check(quan trọng) là giải quyết đc bài toán


      • 0
        theanhy2007  commented on 4:19 p.m. 30 jun, 2022

        Bạn cho mình hỏi phần check là check như thế nào nhỉ ? Bạn chỉ mình được không. Mình cảm ơn!!!


      • 1
        nguyendanghau2006  commented on 9:25 a.m. 7 nov, 2021

        ok