Submission #1781193

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<queue>
#include<ctime>
#define sqr(x) (x)*(x)
using namespace std;
long long n,m,i,j,x,y,sum,vis[1000005];
priority_queue<pair<int,long long>/**/> pq;
int main()
{
	cin>>n;
	x=n;
	while (x)
	{
		m+=x%10;
		x/=10;
	}
	pq.push(make_pair(-1,1));
	while ((!pq.empty()))
	{
		x=pq.top().second;
		y=-pq.top().first;
		pq.pop();
		if (vis[x]) continue;
		vis[x]=1;
		if (y>=m)
		{
			cout<<m;
			return 0;
		}
		if (!(x%n))
		{
			cout<<y;
			return 0;
		}
		for (i=0;i<=9;i++)
		{
			if (!vis[(x*10+i)%n]) pq.push(make_pair(-y-i,(x*10+i)%n));
		}
	}
	cout<<m;
	return 0;
}

Submission Info

Judge Result