問題一覧 > 通常問題

No.1632 Sorting Integers (GCD of M)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 45
作問者 : とりゐとりゐ / テスター : re_re0101re_re0101 遭難者遭難者
5 ProblemId : 6720 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-30 23:24:48

問題文

$1$ 桁の正整数が $N$ 個あります．このうち $i$ は $c_i$ 個です $(1\leq i\leq9)$．これら $N$ 個の整数を並べ替え，それを $N$ 桁の $10$ 進法の整数 $M$ とみなしたとき，$M$ として考えられるものすべての 最大公約数 を求めてください．

ただし，考えられる $M$ が一通りしか存在しないときは，その $M$ を最大公約数とします．また，答えは非常に大きくなる可能性があるので，最大公約数を $10^9+7$ で割った余りを出力してください．

入力

$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$
  • 入力は全て整数である

出力

$M$ として考えられるものすべての最大公約数を求めてください．

サンプル

サンプル1
入力
3
1 1 1 0 0 0 0 0 0
出力
3

$1,2,3$ が $1$ つずつあり，$M$ として考えられるものは $123,132,213,231,312,321$ があります．$\gcd(123,132,213,231,312,321)=3$ です．

サンプル2
入力
3
1 2 0 0 0 0 0 0 0
出力
1

$1$ が $1$ つ，$2$ が $2$ つあり，$M$ として考えられるものは $122,212,221$ があります．$\gcd(122,212,221)=1$ です．

サンプル3
入力
1
0 1 0 0 0 0 0 0 0
出力
2

$M$ として考えられるものは $2$ のみです．$M$ が一通りしか存在しないときは．その $M$ を $10^9+7$ で割った余りを出力してください．

サンプル4
入力
900000000
100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000
出力
9

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