Két sắt

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: qgcd.inp
Output: qgcd.out

Authors:
Problem type
Allowed languages
C++, C++ (Themis)

Sau khi LeVanThuc đột nhập thành công vào ngân hàng, anh ấy tìm thấy n cái két sắt liên tiếp nhau, két thứ i chứa số tiền ai. Anh ta cũng có 1 chiếc chìa khóa có thể kích hoạt một lần. Nếu kích hoạt chìa khóa với mật mã là k thì số tiền lấy được ở mỗi két sẽ là gcd(ai,k). Đụng đến gcd anh ấy lại bắt đầu ngứa nghề và tự hỏi bản thân rằng, nếu giả sử chìa khóa được kích hoạt mật mã là k thì tổng số tiền lấy được ở đoạn từ l đến r sẽ là bao nhiêu? Bạn hãy cùng anh ấy giải quyết bài toán này nhé.

INPUT

  • Dòng đầu tiên gồm 2 số nguyên dương n,q(n105,q105) .
  • Dòng thứ hai gồm n số nguyên dương ai(ai107) .
  • q dòng tiếp theo mỗi dòng gồm 3 số nguyên dương tương ứng là li, riki (li,rin,k104).

OUTPUT

  • q dòng gồm q số nguyên dương là số tiền lấy được với mỗi giả sử của LeVanThuc.

Sample Input

Copy
10 5
16 100 51 21 31 32 65 88 1 95 
10 10 10
2 4 4
5 8 6
9 10 5
9 10 3

Sample Output

Copy
5
6
6
6
2

Subtask

  • 30% số test với n,q103
  • 70% số test còn lại không có ràng buộc thêm

Comments

Please read the guidelines before commenting.


There are no comments at the moment.