代表選考合宿 2023
問題 1

問題文の条件は以下と同値である．

• $n$ の正の約数の並べ替え $b_1,b_2,\dots,b_{d(n)-1}$ と正整数からなる等差数列 $a_1,a_2,\dots,a_{d(n)-1}$ が存在して以下が成立する． $$\gcd(a_i,n)=b_i\quad (i=1,2,\dots,d(n)-1)$$

$n$ がこの条件を満たすとする．$n$ の素因数 $p$ をとり．$v_p(n)=e$ とすると，$n$ の約数であって，$p$ の倍数であるものは $\dfrac{e}{1+e}d(n)$ 個だけある．ここで，$b_i$ が全て $p$ の倍数であることはないので，数列 $\{a_i\}$ の公差は $p$ の倍数でなく，この数列に現れる $p$ の倍数は高々 $\left\lceil \dfrac{d(n)-1}{p}\right\rceil$ 個だけ現れる．よって数列 $\{b_i\}$ に現れる $p$ の倍数の個数について以下の不等式が成り立つ．

$$\left\lceil \dfrac{d(n)-1}{p}\right\rceil\geq \dfrac{e}{1+e}d(n)-1$$

これをもとにすれば，$n$ が持つ最大の素因数を考えれば，求める $n$ は次のいずれかの形で表される．ここで $p,q$ は素数である．

$$pq,\quad 12,\quad 8$$

• $n=pq$ のとき
  $p,q\gt 2$ のとき $a_1=p,a_2=(p+q)/2,a_3=q$ とすればよい．
  $p=2$ のとき $a_1=p,a_2=2p+1,a_3=3p+2$ とすればよい．
• $n=12$ のとき
  $a_1=6,a_2=7,a_3=8,a_4=9,a_5=10$ とすればよい．
• $n=8$ のとき
  $a_1=2,a_2=3,a_3=4$ とすればよい．