LQDOJ Contest #8 - Bài 5 - Bài Toán Hóc Búa

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
_minhduc
Dạng bài
Điểm: 0 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho ba số tự nhiên \(n,a,b\). Ta sẽ định nghĩa cặp \((x,y)\) là cặp số đẹp nếu thỏa mãn tất cả các điều kiện như sau:

  • \(1 \le x \le a\).
  • \(1 \le y \le b\).
  • \((x \times y)\) chia hết cho \((x+y)\) và phép chia đó có kết quả không vượt quá \(n\).
  • \(x\) và \(y\) là hai số tự nhiên.

Yêu cầu: Bạn hãy đếm số cặp \((x,y)\) thỏa mãn yêu cầu đề bài là cặp số đẹp.

Input

  • Chứa ba số tự nhiên lần lượt là \(n,a,b\) \((1 \le n,a,b \le 10^{10})\).

  • Dữ liệu luôn đảm bảo rằng kết quả bài toán không vượt quá \(10^{18}\).

Output

  • In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

  • Subtask \(1\) (\(10\%\) số điểm): Có \(n,a,b \le 2 \times 10^4\).

  • Subtask \(2\) (\(20\%\) số điểm): Có \(n,a,b \le 2.5 \times 10^7\).

  • Subtask \(3\) (\(10\%\) số điểm): Có \(n,a,b \le 2.5 \times 10^8\).

  • Subtask \(4\) (\(10\%\) số điểm): Có \(n,a,b \le 2 \times 10^9\).

  • Subtask \(5\) (\(20\%\) số điểm): Có \(n = 10^{10}\) và \(a = b\).

  • Subtask \(6\) (\(10\%\) số điểm): Có \(n = 10^{10}\).

  • Subtask \(7\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input 
6 12 18
Output 
14
Note
  • Có \(14\) cặp thỏa mãn:
    • \(1:(2,2)\)
    • \(2:(3,6)\)
    • \(3:(4,4)\)
    • \(4:(4,12)\)
    • \(5:(6,3)\)
    • \(6:(6,6)\)
    • \(7:(6,12)\)
    • \(8:(8,8)\)
    • \(9:(9,18)\)
    • \(10:(10,10)\)
    • \(11:(10,15)\)
    • \(12:(12,4)\)
    • \(13:(12,6)\)
    • \(14:(12,12)\)

Bình luận