CF2114F Small Operations

根据算数基本定理，有
$$x = p_1^{a_1} p_2^{a_2} \cdots$$
$$y = p_1^{b_1} p_2^{b_2} \cdots$$
令 $g = \gcd (x,y)$，有：
$$g = p_1^{x_1} p_2^{c_2} \cdots$$
其中，
$$c_n = \min (a_n, b_n)$$
令：
$$m = \frac{x}{g} = p_1^{a_1-c_1} p_2^{a_2-c_2} \cdots$$
$$n = \frac{y}{g} = p_1^{b_1-c_1} p_2^{b_2-c_2} \cdots$$
易知：步数最少的操作顺序一定是 $x \rightarrow g \rightarrow y$，且该步数与操作顺序 $m \rightarrow 1 \rightarrow n$ 的步数相同。这又与 $1 \rightarrow m$ 和 $1 \rightarrow n$ 两个操作顺序的步数之和相同。

推论：对于一个步数最少的操作顺序 $1 \rightarrow r$，其中包含有一个操作顺序 $1 \rightarrow s$，则 $1 \rightarrow s$ 的步数也最少。即，这满足最优子结构的性质。

证明：

考虑采用反证法。若 $1 \rightarrow s$ 的步数不是最少，则一定存在一个步数更少的操作顺序 $1 \rightarrow s$，即存在一个步数更少的操作顺序 $1 \rightarrow r$。矛盾！故原命题得证。

故，考虑 DP。设 $f_i$ 为 $1 \rightarrow i$ 的最少步数。则对 $\forall j$ 满足 $i | j$ 且 $\frac{i}{j} \le k$，有：
$$f_i = \min (f_i, f_j+1)$$
只需考察 $m, n$ 的因子即可。

#include <bits/stdc++.h>
#define MAXN 1000005
#define INF 0xffffff
using namespace std;
int dp[MAXN]={0};
int gcd(int a,int b)
{
    if (b==0)
    {
        return a;
    }
    else
    {
        return gcd(b,a%b);
    }
}
int detect(int n,int k)
{
    for (int i=2;i*i<=n&&i<=k;i++)
    {
        while (n%i==0)
        {
            n/=i;
        }
    }
    if (n>k)
    {
        return n;
    }
    else
    {
        return 1;
    }
}
int dfs(int target,int k)
{
    if (target==1)
    {
        return 0;
    }
    if (dp[target])
    {
        return dp[target];
    }
    if (target<=k)
    {
        return dp[target]=1;
    }
    dp[target]=INF;
    for (int i=k;i>1;i--)
    {
        if (target%i==0)
        {
            dp[target]=min(dp[target],dfs(target/i,k)+1);
        }
    }
    return dp[target];
}
int main()
{
    int T;
    scanf("%d",&T);
    while (T)
    {
        memset(dp,0,sizeof(dp));
        int x,y,k;
        scanf("%d %d %d",&x,&y,&k);
        int dx=detect(x,k);
        int dy=detect(y,k);
        if (dx!=dy)
        {
            printf("-1\n");
        }
        else
        {
            int g=gcd(x,y);
            x/=g;
            y/=g;
            int ansx=dfs(x,k);
            int ansy=dfs(y,k);
            printf("%d\n",ansx+ansy);
        }
        T--;
    }
    return 0;
}