UCLN với N

View as PDF

Points: 100 (p) Time limit: 1.0s Memory limit: 256M Input: stdin Output: stdout

Bạn được cung cấp một số nguyên dương \(N\).

Nhiệm vụ của bạn là đếm số lượng số nguyên dương \(x(1 \le x \le N)\) sao cho \(gcd(x,N) = p\).

\(gcd(a,b)\) là ước chung lớn nhất của a và b.

Input

  • Gồm hai số nguyên dương \(N\)\(p\) \((p \le N)\).

Output

  • Gồm một số nguyên duy nhất là kết quả của bài toán.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(N \le 1000\).
  • Subtask \(2\) (\(50\%\) số điểm): \(N \le 10^6\).

Example

Test 1

Input
6 2
Output
2

Comments


  • 3
    thanhkhoa123    9:08 a.m. 9 aug, 2023

    ua sao xai gcd python ko dc

    1 reply

    • -2
      nguyenanhkietht2    9:55 p.m. 1 apr, 2023

      hi

      1 reply

      • 1
        tula    8:27 p.m. 9 jun, 2022

        bài này trâu cũng full :v


        • 2
          MinhMW10    6:29 p.m. 7 oct, 2021 edited

          Tác giả nên tăng thêm bộ nhớ dành cho Scratch vì Scratch khi làm xong bài nhưng tốn hơi nhiều bộ nhớ!


          • -12
            hongquanyl1    9:33 a.m. 29 may, 2021

            This comment is hidden due to too much negative feedback. Click here to view it.

            1 reply

            • -10
              nqkts001    9:30 a.m. 29 may, 2021

              This comment is hidden due to too much negative feedback. Click here to view it.

              1 reply

              • -7
                nqkts001    9:30 a.m. 29 may, 2021

                This comment is hidden due to too much negative feedback. Click here to view it.