E. XGCD

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản

Đề bài

Khi nghiên cứu về lý thuyết dãy số, Nam đã tìm ra một đặc trưng cho dãy số nguyên dương. Cụ thể, với dãy số a gồm n phần tử, xét lần lượt các phần tử từ 1 đến n , với phần tử i , Nam tính được số b_i bằng gcd(a_1, a_2, a_3,…,a_i) (ký hiệu gcd(a_1, a_2, a_3,…,a_i) để chỉ ƯCLN của các số a_1,a_2,…,a_n ). Dãy số b được gọi là dãy đặc trưng của dãy số a . Dễ nhận thấy rằng một dãy số chỉ có duy nhất một dãy đặc trưng, tuy nhiên, có thể có nhiều dãy số khác nhau nhưng có cùng một dãy đặc trưng.

Bẵng đi một thời gian, một hôm, Nam tìm lại được một file văn bản ghi một dãy số b là một dãy đặc trưng của một dãy số khác. Nam muốn tính số lượng dãy số a\ (1\le a_i≤m) mà có dãy đặc trưng là b .

Yêu cầu: Cho dãy số b\ (1\le b_i≤m ), gọi S là số lượng dãy số a có dãy đặc trưng là dãy b , hãy tính S mod 998244353 .

Chú ý:

  • 1 \le a_i,b_i≤m với mọi i \in [1,n] ;
  • Ước chung lớn nhất (gcd) của hai số là số nguyên dương lớn nhất mà hai số cùng chia hết cho số đó.

Dữ liệu:

  • Dòng đầu tiên gồm hai số nguyên dương n,m ;
  • Dòng thứ hai gồm n số nguyên dương b_1, b_2, b_3,…, b_n\ (1\le b_i≤m) , dãy b đảm bảo luôn có dãy a thỏa mãn.

Kết quả:

  • Một số nguyên duy nhất là giá trị S mod 998244353 .

Ví dụ:

Dữ liệu:

3 5
4 2 1

Kết quả:

3

Giới hạn:

  • Subtask \#1: ( 40\% số điểm): 1 ≤ n, m ≤ 5 ;
  • Subtask \#2: ( 30\% số điểm): 1 ≤ n, m ≤ 2000 ;
  • Subtask \#3: ( 30\% số điểm): 1 ≤ n ≤ 2\times 10^5 ,1 ≤ m ≤ 10^9 .