Problem Description

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

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.

Example

Sample Input 1

6

Sample Output 1

3
12=6×2 yields the smallest sum.

Sample Input 2

41

Sample Output 2

5
11111=41×271 yields the smallest sum.

Sample Input 3

79992

Sample Output 3

36

題意：給出一個整數 k，求這個數的倍數，使得其各位數的和最小，并輸出這個和

思路：bfs

設答案為 x，由于要求 x 的各位數之和最小，那么可以從 1 開始，當搜索到的第一個值 %k 為 0 即為答案

那么有 2 種入隊方式：

• x+1：此時各位數字和比之前的多了一個?1，那么代價是 1
• x*10：此時各位數字和比之前沒有改變，那么代價就是 0

因此問題轉換為用 bfs 找到滿足條件的 x，由于要找各位和最小的，也就是說代價為 0 的首先出隊，因此可以使用雙端隊列，將代價為 0 的放在隊首，代價為 1 的放在隊尾?

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 100000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std; int vis[N]; int main() {int n;scanf("%d",&n);deque<pair<int,int> > Q;Q.push_front(make_pair(1,1));while(!Q.empty()){pair<int,int> temp=Q.front();Q.pop_front();if(!vis[temp.first]){vis[temp.first]=true;if(temp.first==0){printf("%d\n",temp.second);break;}Q.push_front(make_pair((temp.first*10)%n,temp.second));Q.push_back(make_pair((temp.first+1)%n,temp.second+1));}}return 0; }

?

總結

以上是生活随笔為你收集整理的Small Multiple（AtCoder-3621）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。