Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

UCLNPATH - Đường đi không nguyên tố

Cho một lưới ô vuông gồm m dòng và n cột. Các dòng được đánh số từ 1 đến m từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua phải. Ô nằm ở vị trí dòng i và cột j của lưới được gọi là ô (i, j) và khi đó, i được gọi là tọa độ dòng còn j được gọi là tọa độ cột của ô này. Trên ô (i, j) của lưới ghi số nguyên dương aij. Trên lưới đã cho, từ ô (i, j) ta có thể di chuyển đến ô (p, q) nếu UCLN(aij, apq) > 1 và một trong các điều kiện sau đây được thỏa mãn:

  • q = j và i < p ≤ m (đi xuống dưới).
  • i = p và j < q ≤ n (đi sang phải).

Ta gọi một cách di chuyển từ mép trái sang mép phải của lưới là cách di chuyển bắt đầu từ một ô có tọa độ cột bằng 1 qua các ô của lưới theo qui tắc di chuyển đã nêu và kết thúc ở một ô có tọa độ cột bằng n.

Yêu cầu: Tính số cách di chuyển từ mép trái lưới sang mép phải lưới.

Dữ liệu vào:

  • Dòng đầu gồm hai số nguyên dương m và n được ghi cách nhau một dấu cách.
  • m dòng tiếp theo, dòng thứ i chứa n số nguyên dương ai1, ai2, …, ain, hai số liên tiếp được ghi cách nhau một dấu cách.

Dữ liệu ra:

            Một số nguyên dương duy nhất là số cách di chuyển từ mép trái lưới sang mép phải lưới (do số này có thể rất lớn nên chỉ lấy phần dư khi chia cho 1000000007).

Ví dụ:

Dữ liệu vào:
2 2
2 4
6 8
Dữ liệu ra:
4

Giải thích: Các cách đi là:

  • Cách 1: (1, 1)(1, 2)
  • Cách 2: (1, 1)(1, 2) →(2, 2)
  • Cách 3: (2, 1) →(2, 2)
  • Cách 4: (1, 1)(2, 1) →(2, 2)

Giới hạn: 1 < m, n ≤ 100; 1≤ aij ≤ 30000.


Được gửi lên bởi:noname00.pas
Ngày:2017-06-30
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C-CLANG C CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 JAVA PAS-FPC PYTHON PYTHON3
Nguồn bài:Bài tập thực hành CSL

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.