欢迎访问 如意编程网!

如意编程网

当前位置: 首页 > 编程资源 > 综合教程 >内容正文

综合教程

Small Multiple

发布时间:2023/10/11 综合教程 20 老码农
如意编程网 收集整理的这篇文章主要介绍了 Small Multiple 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

题目描述

Find the smallest possible sum of the digits in the decimal notation of a positive multiple of K.
Constraints
2≤K≤105
K is an integer.

输入

Input is given from Standard Input in the following format:
K

输出

Print the smallest possible sum of the digits in the decimal notation of a positive multiple of K.

样例输入

6

样例输出

3

提示

12=6×2 yields the smallest sum.

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int N=3e5+;
const int p=1e9+;
int k,cnt;
int dis[N],last[N];
bool vis[N];
struct orz{
int v,nex,s;}e[N*];
queue<int>q;
void add(int x,int y,int z)
{
cnt++;
e[cnt].v=y;
e[cnt].nex=last[x];
last[x]=cnt;
e[cnt].s=z;
}
void spfa()
{
for (int i=;i<k;i++) dis[i]=inf;
dis[]=; vis[]=;
q.push();
while (!q.empty())
{
int now=q.front(); q.pop();
for (int i=last[now];i;i=e[i].nex)
{
if (dis[e[i].v]>dis[now]+e[i].s)
{
dis[e[i].v]=dis[now]+e[i].s;
if (!vis[e[i].v])
{
vis[e[i].v]=;
q.push(e[i].v);
}
}
}
vis[now]=;
}
}
int main()
{
scanf("%d",&k);
for (int i=;i<k;i++)
{
add(i,(i+)%k,);
add(i,i*%k,);
} spfa(); printf("%d\n",dis[]+);
return ;
}

总结

以上是如意编程网为你收集整理的Small Multiple的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得如意编程网网站内容还不错,欢迎将如意编程网推荐给好友。