题目：P10494。

得分情况

#include <bits/stdc++.h>
#define PII pair <int, int>
#define PDII pair <PII, PII>
#define ULL unsigned LL
#define LL long long
#define x first
#define y second

using namespace std;

const int P = 20010;
priority_queue <PDII, vector <PDII>, greater <PDII> > q;
unordered_set <ULL> vis;
int p;

ULL syn(ULL x, ULL y)
{ return x * P + y; }
int gcd(int x, int y)
{ return y ? gcd(y, x % y) : x; }
int f(int x)
{ int res = 0; while(x < p) x <<= 1, res ++ ; return res; }

void add(int a, int b, int step)
{
    if(a < b) swap(a, b);
    if(a == b) return ;
    if(a > P || b > P) return ;
    if(b && (p % gcd(a, b) != 0)) return ;
    if(!vis.count(syn(a, b)))
    {
        vis.insert(syn(a, b));
        q.push({{step + f(a), step}, {a, b}});
    }
}

int bfs(int p)
{
	vis.insert(syn(1, 0));
	q.push({{f(1), 0}, {1, 0}});
	
	while(q.size())
	{
	    PDII t = q.top(); q.pop();
	    int a = t.y.x, b = t.y.y;
	    int step = t.x.y;
	    
	    if(a == p)
	        return step;
	    
	    step ++ ;
	    add(a, a + a, step);
	    add(a, b + b, step);
	    add(a, a + b, step);
	    add(a, a - b, step);
	    add(b, a + a, step);
	    add(b, b + b, step);
	    add(b, a + b, step);
	    add(b, a - b, step);
	}
	
	return -1;
}

signed main()
{
    scanf("%d", &p);
    
    printf("%d", bfs(p));
    
	return 0;
}