| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P152SUMD - ROUND 2D - Lại là ước chung lớn nhất |
Cho dãy số nguyên a[1], a[2], …, a[n] và Q truy vấn. Mỗi truy vấn bạn cần đếm số cặp (L, R) thỏa mãn 1 <= L <= R <= n và gcd(a[L], a[L+1], a[L+2], …, a[R]) = x với x là số nguyên cho trước.
Gcd(v[1], v[2], …, v[n]) là ước số chung lớn nhất của v[1], v[2], …, v[n].
Input
Dòng đầu chứa số nguyên dương n(1 <= n <= 10^5).
Dòng tiếp theo chứa dãy a[1], a[2], .. , a[n], mỗi số cách nhau bởi 1 dấu cách và có giá trị không vượt quá 10^9.
Dòng thứ 3 chứa số nguyên dương Q (1 <= Q <= 3*10^5).
Q dòng tiếp theo mỗi dòng chứa 1 số x tương ứng (1 <= x <= 10^9).
Output
Với mỗi truy vấn, ghi kết quả trên 1 dòng tương ứng.
Example
Input:3
2 6 3
5
1
2
3
4
6
Output:1
2
2
0
1
| Được gửi lên bởi: | adm |
| Ngày: | 2015-07-08 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
