COUNT - COUNT
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: only_love97

Cho số nguyên N yêu cầu đếm số lượng giá trị khác nhau của số nguyên x sao cho:

+ 1<=x <= N

+ các phần tử thuộc dãy u khác nhau đôi một.

+ dãy (u) có N phần tử được định nghĩa riêng với mỗi giá trị x như sau:

u1 = 1

ui = (ui-1+x)%N, với i=2->N

 

Input:

Dòng 1: Số nguyên T, là loại test đưa ra. (1<=T<=2)

Với T=1:

Dòng 2: Gồm một số nguyên N được tạo thành từ tích 3 số nguyên có giá trị không nhỏ hơn 10^4 (10^12<=N<=10^16).

Với T=2:

Dòng 2: Gồm hai số nguyên p và k, giá trị của N được tính theo công thức N=pk. (1<=p<=1012, 1<=k<=1018)

Dữ liệu đảm bảo N>1.

Output:

Kết quả bài toán, do kết quả có thể rất lớn nên chỉ cần in ra phần dư cho 109.

Ví dụ

  • input
    2
    2 2
    output
    2
  • input
    1
    1000000000000
    output
    0
Back to Top