Tam giác vuông trên vòng tròn

Xem dạng PDF

Gửi bài giải


Điểm: 0,62 (OI)
Giới hạn thời gian: 0.9s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
SRM 473, Div 1 - Level 2Người dịch: Ngô Minh Ðức
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho ~N~ điểm cách đều nhau trên một vòng tròn được đánh số từ ~0~ đến ~N - 1~ theo chiều kim đồng hồ, trong đó có ~P~ điểm được sơn màu đỏ. Hãy đếm số tam giác vuông có ~3~ đỉnh đều được sơn màu đỏ.

Biết rằng ~P~ điểm màu đỏ được tạo thành như sau, cho trước ~3~ số nguyên ~a~, ~b~, ~c~. Với ~i = 0~, ~1~, ~2~, ~3~, ~\cdots~, ~P - 1~, thực hiện các bước sau:

  • Tính ~P[i]~ ~=~ ~(a \times i \times i + b \times i + c)~ mod ~N~.
  • Bắt đầu từ ~P_i~, tìm điểm đầu tiên theo chiều kim đồng hồ mà chưa được sơn đỏ và sơn đỏ điểm đó

Input

  • Mỗi test bắt đầu bằng thẻ [CASE], các test cách nhau bởi một dòng trắng. Thẻ [END] báo hiệu kết thúc file input.
  • Mỗi test gồm ~5~ dòng chứa các số ~N~, ~P~, ~a~, ~b~, ~c~ ~(1 \leq N \leq 10^6, 0 \leq P \leq 10^5, 0 \leq a, b, c \leq 10^6)~.

Output

  • Với mỗi test in ra số tam giác vuông tìm được.

Sample Input

[CASE]
9
3
0
3
0

[CASE]
40
3
5
0
0

[CASE]
4
4
16
24
17

[CASE]
1000000
47000
0
2
5

[CASE]
200000
700
123456
789012
345678

[END]

Sample Output

0
1
4
0
6980

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.