Atcoder arc 084 D - 小倍数（双队列+抽屉原理）

题目对应的网络地址为：http://arc084.contest.atcoder.jp/tasks/arc084_b>

D - Small Multiple

Time limit : 2sec / Memory limit : 256MB

Score : 700 points

Problem Statement

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

Constraints

• 2≤ K ≤105
  • K 属于整数集合。

Input

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.

Sample Input 1

Copy