Cho trước hai số nguyên dương m và n với 1< m ≤ 10^15 ; 1 < n ≤ 10^7 . Hãy xác định có bao nhiêu cặp số nguyên dương (p; q) thỏa mãn đồng thời cả 3 điều kiện: p < m; q < n và phân số (m+p)/(n+q) có giá trị là một số nguyên. Dữ liệu vào: Từ file văn bản PSNGUYEN.INP gồm: - Dòng thứ nhất chứa số nguyên dương m (1< m ≤ 10^15) - Dòng thứ hai nguyên dương n (1< n ≤ 10^7) Kết quả: Ghi ra file văn bản PSNGUYEN.OUT một số nguyên k là số cặp số nguyên dương (p;q) thỏa yêu cầu trong đề bài Ví dụ: PSNGUYEN.INP PSNGUYEN.OUT 5 1 3

1 câu trả lời

Gọi `f(q) = k` `(q < n)` là số nghiệm p thỏa mãn: `m + p \vdots n + q`
`=> S = \sum_{q = 1}^{n - 1} f(q)`
Tự chứng minh: `p_1 = (n + q) - (m mod (n + q))`
`p_i = p_(i - 1) + (n + q) (∀ 2 le i le k)` 

uses crt;
var m, p, res: int64;
    n, q: longint;

function f(q: longint): int64;
begin
    p:=(n + q) - (m mod (n + q));
    if p >= m then exit(0);
    exit((m - p - 1) div (n + q) + 1);
end;
    
begin
    readln(m, n);
    for q:=1 to n - 1 do begin
        inc(res, f(q));
    end;
    writeln(res);
readln;
end.

Câu hỏi trong lớp Xem thêm