AT3621 ARC084D Small Multiple 题解【01BFS】【同余】

点击量：244

    把一个数学题建成一个图论题 

目录

Problem Statement

Find the smallest possible sum of the digits in the decimal notation of a positive multiple of \(K\).

 

Constraints

• \(2\le K\le 10^5\)
• \(K\) is an integer.

---

Input

Input is given from Standard Input in the following format:

K

Output

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

---

Sample Input 1

6

Sample Output 1

3

\(12=6\times 2\) yields the smallest sum.

---

Sample Input 2

41

Sample Output 2

5

\(11111=41\times 271\) yields the smallest sum.

---

Sample Input 3

79992

Sample Output 3

36

题意：

    给定一个正整数\(K\)，求出一个\(S\)使得\(K|S\)且\(K_{(10)}\)的各位相加和最小，并输出这个最小的和。

题解：

    也许是个数位取模题的套路吧。在数位中\(\times 10\)的贡献是\(0\)，\(+1\)的贡献是\(1\)。比如从\(8\)转移到\(9\)，发现数位和加了\(1\)，从\(8\)转移到\(80\)，数位和不变。

    然后在\(\pmod K\)的意义下建图，跑\(1\bmod K\)到\(0\bmod K\)的最短路，而且实际上\(1\bmod K\)的初始状态并不一定就出现在答案中，它可以\(+1\)贡献转化为\(2\bmod K\)。最短路的意义就是产生一个能整除\(K\)的正整数在数位上所需的最小代价。这种题其实就是个套路吧…不过以后要常把各种问题结合到图上，建立图论模型来分析问题。

    然后这个题可以\(O(n+m)=O(n)(m\approx 2n)\)解决，就是使用\(\tt 01BFS\)。\(\tt 01BFS\)是可以在权值仅为\(1\)或\(0\)的图上\(O(n+m)\)求出单源最短路的高效算法。其思路类似分层或者\(\tt SPFA\)的\(\tt LLL\)优化，和\(\tt Dijkstra\)效果类似，要用到双端队列，建议手写。每个点进队唯一一次，当且仅当它的最短路已经被更新到，如果一个点被边权为\(0\)的边引入队列，放在队列的最前，否则放在最后，保证了每次从队首取出来的是当前队中距离源点最短的节点。最后输出\(dis[0]\)即可，不过这个题\(\tt Dijkstra\)在\(O(k\log k)\)的复杂度内也是可以完成的。

Code：

#include<cstdio>
#include<cstring>
struct edge
{
    int n,nxt,v;
    edge(int n,int nxt,int v)
    {
        this->n=n;
        this->nxt=nxt;
        this->v=v;
    }
    edge(){}
}e[200010];
int head[100010],ecnt=-1;
void add(int from,int to,int v)
{
    e[++ecnt]=edge(to,head[from],v);
    head[from]=ecnt;
}
int q[200100],l=100000,r=100000;
int dis[100100];
int main()
{
    memset(head,-1,sizeof(head));
    memset(dis,0x3f,sizeof(dis));
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i)//连边，其实可以不用连，每个点出度为2，在后面枚举即可
    {
        add(i,(i+1)%n,1);
        add(i,i*10%n,0);
    }
    q[++r]=1;
    dis[1]=1;
    while(l<r)
    {
        int x=q[++l];
        for(int i=head[x];~i;i=e[i].nxt)//Dijkstra的过程
            if(dis[e[i].n]>dis[x]+e[i].v)
            {
                dis[e[i].n]=dis[x]+e[i].v;
                if(e[i].v)
                    q[++r]=e[i].n;//进队
                else
                    q[l--]=e[i].n;
            }
    }
    printf("%d\n",dis[0]);
    return 0;
}