01/10/2018, 15:44
Cách làm tối ưu của bài toán tính mod
Đây là đầu bài ạ : Hôm nay, Lúi đăng kí tham gia chương trình Ai thông minh hơn học sinh lớp 5. Cậu đang tranh tài cùng với một em học sinh lớp 5 và câu hỏi được đưa ra là: với 2 số nguyên không âm a và b, có bao nhiêu số nguyên không âm x mà a % x = b. Bạn hãy giúp Lúi trả lời thật nhanh câu hỏi này để giành được điểm nhé.
VD:
Input:
11 2
Output:
2
Mọi người có thể cho e ý tưởng về hướng giải bài này tối ưu được ko ạ ? E cảm ơn
Bài liên quan
a chia x dư b nghĩa là a = cx + b. Đề bài chuyển về tìm cx = a - b, điều kiện của cx là x > b, c bất kì. Bài toán chuyển về tìm các ước của hiệu a - b sao cho ước này > b
Vd a = 49 b = 4 thì hiệu a - b = 45 có 6 ước 1 3 5 9 15 45. Trong 6 ước này chỉ có 4 ước (5 9 15 45) thỏa điều kiện lớn hơn b=4 nên có 4 số x mà 45 % x = 4