(USACO) D - Small Multiple

#include <bits/stdc++.h>

using namespace std;
// #define int long long
#define ld long double
#define F first
#define S second
#define el '\n'
#define cout(x) for(auto v:x)cout<<v<<' ';cout<<el
#define coutp(x) for(auto v:x)cout<<v.F<<' '<<v.S<<el
#define cin(x) for(auto &v:x)cin>>v;
#define all(x)  x.begin(),x.end()
#define ll long long
#define sz(x)  (int)x.size()
#define pi pair<ll,ll>
using ull = unsigned long long;
const int N=1e5+5;
ll dis[N];
void solve(){

    ll k;
    cin>>k;

    for (int i=0;i<N;i++)dis[i]=1e9;
    priority_queue<pi,vector<pi>,greater<pi>>pq;
    for (int i=1;i<=9;i++)
    {
        ll r=i%k;
        if (i<dis[r])
        {
            dis[r]=i;
            pq.push({i,r});
        }
    }

    while (!pq.empty())
    {
        auto [d,r]=pq.top();
        pq.pop();
        // cout<<d<<" "<<r<<"\n";
        if (d!=dis[r])continue;
        if (r==0){
            cout<<d<<"\n";
            return;
        }

        for (int i=0;i<=9;i++)
        {
            ll nr=(r*10+i)%k;
            ll nc=d+i;
            if (nc<dis[nr])
            {
                pq.push({nc,nr});
                dis[nr]=nc;
            }
        }

    }
}

int32_t main()
{

#ifndef ONLINE_JUDGE
     freopen("in.txt", "r", stdin);
     //freopen("output.txt", "w", stdout);
#endif


    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tc = 1;
    //cin >> tc;
    for (int i = 1; i <= tc; i++)solve();
    return 0;
}
/*

 */