| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P164SUMJ - ROUND 4J - Phép chia |
Cho một dãy số có n phần tử a[1], a[2], …, a[n] và m cặp số (p[1], q[1]), (p[2], q[2]), …, (p[m], q[m]).
M Cặp số này có đặc điểm tổng các phần tử mỗi cặp số là một số lẻ và 1 <= p[i] < q[i] <= n
Bạn có thể thực hiện một thao tác như sau:
+ Bước 1: Chọn ra một cặp số bất kì trong m cặp số giả sử là (p[k], q[k]) và một số v (v > 1) sao cho v là ước chung của a[p[k]] và a[q[k]]
+ Bước 2: Lấy a[p[k]] và a[q[k]] chia cho v hay a[p[k]] = a[p[k]] / v và a[q[k]] = a[q[k]] / v.
Bạn hãy tìm cách thực hiện thao tác sao cho thực hiện được nhiều lần nhất có thể.
Input
Dòng đầu tiên gồm 2 số nguyên n, m (2 <= n <= 100, 1 <= m <= 100).
Dòng thứ 2 gồm n số nguyên a[1], a[2], …, a[n] (1 <= a[i] <= 10^9, 1 <= i <= n).
m dòng tiếp theo, dòng thứ I chứ cặp số nguyên (p[i], q[i])
Output
Số thao tác lớn nhất thực hiện được.
Example
Input:
6 4
35 33 46 58 7 61
4 5
3 6
5 6
1 6
Output:
0
| Được gửi lên bởi: | adm |
| Ngày: | 2016-07-29 |
| 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 JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
