問題一覧 > 通常問題

No.1632 Sorting Integers (GCD of M)

レベル : / AI推定難易度 : 1625 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 47
作問者 : とりゐ / テスター : re_re0101 👑 qand
お気に入りにしたユーザー ProblemId : 6720 / 自分の提出
問題文最終更新日: 2021-07-30 23:24:48
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 307 (順位表) の他の問題:

Problem Statement

There are $N$ positive integers of $1$ digit each. Among them, the number of integers equal to $i$ is $c_i$ $(1\leq i\leq9)$. Rearrange these $N$ integers and regard the result as an $N$-digit integer $M$ in base $10$. Find the greatest common divisor of all possible values of $M$.

Here, if there is only one possible value of $M$, that $M$ is taken as the greatest common divisor. Since the answer can be very large, output the greatest common divisor modulo $10^9+7$.

Input

$N$
$c_1\ c_2\ c_3\ c_4\ c_5\ c_6\ c_7\ c_8\ c_9$

  • $1\leq N\leq 10^9$
  • $c_i\geq0$
  • $\displaystyle \sum_{i=1}^9 c_i=N$
  • All input values are integers.

Output

Find the greatest common divisor of all possible values of $M$.

Sample

Sample 1
Input
3
1 1 1 0 0 0 0 0 0
Output
3

Each of $1,2,3$ appears $1$ time, and the possible values of $M$ are $123,132,213,231,312,321$. We have $\gcd(123,132,213,231,312,321)=3$.

Sample 2
Input
3
1 2 0 0 0 0 0 0 0
Output
1

The digit $1$ appears $1$ time and the digit $2$ appears $2$ times, and the possible values of $M$ are $122,212,221$. We have $\gcd(122,212,221)=1$.

Sample 3
Input
1
0 1 0 0 0 0 0 0 0
Output
2

The only possible value of $M$ is $2$. When there is only one possible value of $M$, output that $M$ modulo $10^9+7$.

Sample 4
Input
900000000
100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000
Output
9

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。