Bờm viết số 293 sau đó tính tổng bình phương các chữ số của số này và lấy kết quả đó thay thế cho số hiện tại: 22 + 92 + 32 = 94. Bờm tiếp tục lặp lại quá trình trên đến khi nhận được số 1 thì dừng: 94 → 97 → 130 → 10 → 1. Bờm gọi những số khi thực hiện quá trình như trên mà kết quả cuối cùng là số 1 là số đặc biệt. Bờm muốn biết trong đoạn [l,r] có bao nhiêu số đặc biệt
Câu 5: Số đặc biệt (PEARL)
Bờm viết số 293 sau đó tính tổng bình phương các chữ số của số này và lấy kết quả đó thay thế cho số hiện tại: 22 + 92 + 32 = 94. Bờm tiếp tục lặp lại quá trình trên đến khi nhận được số 1 thì dừng: 94 → 97 → 130 → 10 → 1. Bờm gọi những số khi thực hiện quá trình như trên mà kết quả cuối cùng là số 1 là số đặc biệt. Bờm muốn biết trong đoạn [l,r] có bao nhiêu số đặc biệt.
Yêu cầu: với mỗi cặp số nguyên l,r (1≤l≤ r ≤1018), xác định số lượng số đặc biệt nằm trong đoạn [l,r].
Dữ liệu: vào từ file văn bản PEARL.INP:
• Dòng đầu chứa số nguyên dương t là số lượng đoạn cần xác định số lượng số đặc biệt;
t dòng tiếp theo, mỗi dòng chứa hai số l, r.
Kết quả: ghi ra file văn bản PEARL.OUT gồm t dòng, mỗi dòng chứa một số nguyên là kết quả tìm được tương ứng.
Ví dụ:
PEARL.INP
PEARL.OUT
1
1
Giới hạn:
2941999 2942002
Có 20% số test có t ≤ 30 và r - l ≤ 106.
Có 20% số test có t ≤ 100; 1 ≤l≤ r ≤ 109.
Có 60% số test có t ≤ 100; 1 ≤l≤ r ≤ 1018.
• làm trong c++