思路：
这道题是个图论抽象的题目……
考场上想到了没写对……
我们发现，f函数转移的方式有两种，要么是代价10的+1，要么是代价1的乘一个质因数
那么我们就可以将这个抽象为一张图
每个i向每个i+1连一条边权为10的边
每个i向每个i*质因子[j]连一条边权为1的边
跑最短路即可
跑完最短路就是状压搜索
加上最优化剪枝和记忆化剪枝即可
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define rii register int i
#define rij register int j
#define int long long
using namespace std;
int k,dp[];
int ans,sl,ss[],sk,s[],minx,head[],cnt,jl[];
int fin=,dis[];
struct uio{
int nxt,to,val;
}x[];
void add(int from,int to,int val)
{
cnt++;
x[cnt].to=to;
x[cnt].val=val;
x[cnt].nxt=head[from];
head[from]=cnt;
}
//void dfs(int p,int q,int dj,int sd)
//{
// if(sd>100)
// {
// return;
// }
// if(dj>ans)
// {
// return;
// }
// if(q==0)
// {
// ans=min(ans,dj);
// return;
// }
// dfs(p,(q+1)%p,dj+10,sd+1);
// for(rii=1;i<=sl;i++)
// {
// dfs(p,(q*s[i])%p,dj+1,sd+1);
// }
//}
void djstl(int wz)
{
for(rii=head[wz];i!=;i=x[i].nxt)
{
if(dis[x[i].to]>dis[wz]+x[i].val)
{
dis[x[i].to]=dis[wz]+x[i].val;
djstl(x[i].to);
}
}
}
void cf(int val)
{
cnt=;
memset(head,,sizeof(head));
sl=;
for(rii=;i<=val;i++)
{
if(val%i==)
{
val/=i;
if(s[sl]!=i)
{
sl++;
s[sl]=i;
i--;
}
}
if(val==)
{
return;
}
}
}
int f(int val)
{
cnt=;
memset(x,,sizeof(x));
memset(head,,sizeof());
memset(dis,0x3f,sizeof(dis));
int p=,q=,ltt=val;
while(ltt>)
{
p+=ltt%;
ltt/=;
}
p+=;
ltt=val;
while(ltt>)
{
q*=ltt%;
ltt/=;
}
cf(val);
q+=;
q%=p;
for(rii=;i<p;i++)
{
for(rij=;j<=sl;j++)
{
add(i,i*s[j]%p,);
}
add(i,(i+)%p,);
}
dis[q]=;
djstl(q);
return dis[];
}
void cfk(int val)
{
sk=;
for(rii=;i<=val;i++)
{
if(val%i==)
{
val/=i;
if(ss[sk]!=i)
{
sk++;
ss[sk]=i;
i--;
}
}
if(val==)
{
return;
}
}
}
inline int gtv(int v)
{
int kkk=,cnt=;
while(v!=)
{
cnt++;
if(v%==)
{
kkk*=ss[cnt];
}
v/=;
}
return kkk;
}
void kfs(int zt,int dj)
{
if(dp[zt]>dj)
{
dp[zt]=dj;
}
else
{
return;
}
if(dj>=fin)
{
return;
}
if(dj<fin&&zt==(<<sk)-)
{
fin=dj;
return;
}
for(rii=;i<=(<<sk)-;i++)
{
if((zt&i)==)
{
kfs(zt|i,dj+f(gtv(i)));
}
}
}
signed main()
{
freopen("k.in","r",stdin);
freopen("k.out","w",stdout);
memset(dp,0x3f,sizeof(dp));
cin>>k;
cfk(k);
if(sk==)
{
cout<<f(k);
return ;
}
fin=f(k);
kfs(,);
cout<<fin;
}