30/09/2018, 18:24
Tìm số lượng cặp (x, y) thỏa mãn để P là số nguyên tố, với 0 <= x <= N cho trước (N<=10^7)
Cho P được định nghĩa như trên. Tìm số lượng cặp (x, y) thỏa mãn để P là số nguyên tố với x không âm và nhỏ hơn hoặc bằng số N cho trước (N<=10^7).
Input: Nhập vào số N;
Ouput: In ra số lượng cặp (x, y) thỏa mãn.
TIme Limit: 2s.
Bài này em có thử phân tích ra nhưng cho N từ 10^5 trở đi thì chạy quá thời gian.
Mọi người cho em xin hướng để giải quyết với.
Bài liên quan
Trong đề này thì x không âm và cái gì nhỏ hơn hoặc bằng N cho trước?
Dạ x không âm và x <=N đó a
Mà x, y đều là số nguyên hết
Đã sửa lại tiêu đề cho dễ hiểu
Thank a
Đây là một bài trong đợt test ACM miền bắc vừa qua, do có ít đội làm được quá nên không biết tham khảo ai :)))
cái P kia phân tích được thành P=(x-y)(2x^2+3(x-y)) thì không bao giờ là nguyên tố còn gì vì nó luôn chia hết cho(x-y) hoặc (2x^2+3(x-y)) , không biết em nghĩ vậy có đúng không ạ ?
Được đó bạn, khi 1 trong trong 2 cái =1 còn cái kia là 1 số nguyên tố, hoặc 1 cái = -1, cái kia là -(số nguyên tố)
Có 4 TH thừa số trái hoặc phải =±1 từ đó suy ra y trong mỗi TH đó
for 4 vòng của x: kiểm tra nto = rabin miller dpt NlogN