DIVISORPART

View as PDF

Submit solution


Points: 100.00
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Cho một dãy số nguyên A gồm N phần tử, các phần tử được đánh số từ 1 đến N .

Nếu phần tử Ai là ước của phần tử Ai+1(i<n) thì hai phần tử này thuộc cùng một vùng. Dễ nhận thấy rằng mỗi phần tử chỉ thuộc vào một vùng duy nhất. Gọi Si là chỉ số nhỏ nhất của các phần tử cùng chung một vùng với phần tử Ai.

Yêu cầu thực hiện Q truy vấn thuộc một trong hai loại:

  • Loại 1 có dạng 1 i X: Đổi giá trị Ai thành X (1iN,1X106).
  • Loại 2 có dạng 2 i: Tìm giá trị Si (1iN).

Dữ liệu

  • Dòng đầu chứa hai số nguyên dương là NQ (N106,Q2·105).
  • Dòng thứ hai chứa N số nguyên là dãy A (1Ai106).
  • Mỗi dòng trong Q dòng tiếp theo là một truy vấn thuộc một trong hai loại trên.

Kết quả

  • Với mỗi truy vấn loại 2, in một dòng chứa một số nguyên duy nhất là kết quả của truy vấn.

Ví dụ

Sample Input 1
Copy
5 5
2 2 7 14 14
1 1 3
1 2 6
2 2
2 4
2 5
Sample Output 1
Copy
1
3
3

Chấm điểm

  • Subtask 1 (60% số test): Độ dài của một vùng bất kì luôn nhỏ hơn 100.
  • Subtask 2 (40% số test): Không có ràng buộc gì thêm.

Nguồn: Beginner Free Contest 30


Comments

Please read the guidelines before commenting.


There are no comments at the moment.