Submission #1781340

---

Source Code Expand

//by sdfzchy
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
const int inf=(1<<30),N=100010;
int k,m,dis[N];
bool vis[N];
inline int in()
{
	char ch=getchar();
	int f=1,tmp=0;
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {tmp=(tmp<<1)+(tmp<<3)+(ch-'0');ch=getchar();}
	return tmp*f;
}

int main()
{
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	k=in();
	for(int i=0;i<=k;i++) dis[i]=inf;
	dis[1]=1;
	queue<int> q;
	q.push(1);
	vis[1]=1;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		if(dis[x]+1<dis[(x+1)%k])
		{
			dis[(x+1)%k]=dis[x]+1;
			if(!vis[(x+1)%k]) vis[(x+1)%k]=1,q.push((x+1)%k);
		}
		if(dis[x]<dis[x*10%k])
		{
			dis[x*10%k]=dis[x];
			if(!vis[x*10%k])  vis[x*10%k]=1,q.push(x*10%k);
		}
	}
	printf("%d",dis[0]);
	return 0;
}

Submission Info

Judge Result