問題一覧 > 通常問題

No.1632 Sorting Integers (GCD of M)

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

問題文

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

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

入力

N
c1 c2 c3 c4 c5 c6 c7 c8 c9

  • 1≤N≤109
  • ci≥0
  • ∑i=19ci=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 を 109+7 で割った余りを出力してください．

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

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