---
author: nguyencter
tags: Trans
title: Trans Solution
---

$\Huge\text{Trans Solution}$

-------

:::info
🔗 Links: [Đề bài](https://drive.google.com/file/d/1EDCLctPhuW3Nnz2dGrvbtbIdIseOB5Yv/view?usp=sharing)
📌 Tags: `dp`
✍️ Writer: nguyencter
📋 Content:
[TOC]
:::

-----

## Giới Thiệu Đề Bài


-----

## Thuật toán

Ta có nhận xét : số phép biến đổi $a$ thành $b$ $=$ (số phép biến đổi từ $gcd(a,b)$ thành $a$)$+$(số phép biến đổi từ $gcd(a,b)$ thành $b$).

Gán $a'=a/gcd(a,b)$ và $b'=b/gcd(a,b)$

Ta thấy số phép biến đổi $a$ thành $b$ bằng số phép biến đổi $a'$ thành $b'$ nên ta chỉ cần tìm số phép biến đổi $a'$ thành $b'$ là được.

Để tính số phép biến đổi từ $1$ đến $a'$ ta sử dụng phương pháp quy hoạch động.

Gọi mảng $f$ gồm $k$ phần tử là mảng chứa các ước số của $a'$ được sắp xếp tăng dần.

Gọi $dp[i]$ là số phép biến đổi từ $1$ thành ước số lớn thứ $i$ của $a'$

Bài toán cơ sở: $dp[1]=0$.

$dp[i]=min(dp[j])+1$ với $j<i,$ $f[i]$ % $f[j]=0,f[i]/f[j] \leq d$.

Gọi $dp'[i]$ là số phép biến đổi từ $1$ thành ước số lớn thứ $i$ của $b'$

Mảng $dp'$ tính toán tương tự mảng $dp$.

Kết quả bài toán là $dp[k]+dp'[k'].$

Vì số lượng ước lớn nhất của $a'$ và $b'$ không quá 2000 nên độ phức tạp của thuật toán trên là khoảng $O(2000^2)$.

----

Tham khảo code ở [đây](https://github.com/nguyencter/CODE/blob/main/bwpoints.cpp)