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

作者: wjyyy 分类: 01BFS,同余,图论,最短路,解题报告 发布时间: 2018-10-22 22:04

点击量:32

 

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

 

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;
}

说点什么

avatar
  Subscribe  
提醒
/* */