UCLN với N

Xem PDF
Tác giả:
algorit , bin9638
Dạng bài
Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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\) và \(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

Bình luận


  • -11
    nqkts001    9:30 a.m. 29 Tháng 5, 2021

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


    • -2
      duyanhloveav    9:32 a.m. 29 Tháng 5, 2021

      gì


      • -9
        nqkts001    9:41 a.m. 29 Tháng 5, 2021

        Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


        • 0
          HaiNguyen2307    5:23 a.m. 3 Tháng 4, 2023

          Bạn ơi , đây đâu phải chat đâu? hỏi trong chat đi


          • -8
            duyanhloveav    7:06 p.m. 6 Tháng 6, 2021

            Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

        6 bình luận nữa