約数と倍数

概要

$2$ つの整数 $a$ と $b$ の間に、$a$ を $b$ で割った時に余りが出ないという関係が成り立つことがある。
このとき、$a$ に注目すれば「$a$ は $b$ の倍数である」、$b$ に注目すれば「$b$ は $a$ の約数である」という。

数学の世界ではもちろん、プログラミングでもこの考え方は重要で、様々な応用が存在する。

倍数判定（A問題相当）

A問題から使われる、「$a$ が $b$ の倍数である場合」という判定。
これはつまり、$a$ を $b$ で割った余りが $0$ かということなので、以下のように書けばよい。
$b$ を $2$ にすれば、「$a$ が偶数である場合」という判定になる。

if (a%b==0) {
  // 倍数のときにしてほしい処理
}

また、「$a$ が $b$ の倍数でない場合」と書きたい場合は、以下のいずれか。
上の方が初心者にはわかりやすい。
下は、if文に整数を渡した場合に、$0$ なら false、それ以外なら true と判断する仕様を利用している。
いずれも、$b$ を $2$ にすれば、「$a$ が奇数である場合」という判定になる。

if (a%b!=0) {
  // 倍数でないときにしてほしい処理
}

if (a%b) {
  // 倍数でないときにしてほしい処理
}

これらはそのまま「$b$ が $a$ の約数である場合」「$b$ が $a$ の約数でない場合」としても使える。

倍数生成（A問題相当）

$a$ になるべく近い $b$ の倍数が欲しいことがある。
その場合は、$a$ を $b$ で割り、端数を切り上げ/切り捨て/四捨五入してから $b$ をかければよい。
端数処理はif文などで頑張って書いてもよいが、四則演算だけでも以下のように処理できる。
ただし、$a>0,b>0$ とする。

int m = a/b*b;  // 切り捨てているので、a以下の中では最大の値を探す

int m = (a+b-1)/b*b;  // 切り上げているので、a以上の中では最小の値を探す

int m = (a+b/2)/b*b;  // 四捨五入しているので、大小問わずにaに最も近い値を探す

約数列挙その1（B問題相当）

ある正の整数 $n$ の正の約数を全て列挙したい場合。
まず、$n$ が小さい場合、$1$ から $n$ まで全てについて約数判定をすればよい。
$n$ が $1000000$ くらいまでのものを $1$ つ処理するのは十分高速。

vector<int> divisors;

for (int i=1; i<=n; i++) {
  if (n%i==0) divisors.emplace_back(i);
}

約数列挙その2（C問題相当）

前項目のコードでは、計算量が $O(n)$ であり、$n$ の値が $10^{12}$ などの場合に対しては使えない。
そこで、少し工夫をして $O(\sqrt{n})$ に高速化する。

$n$ の約数は、基本的にかけあわせると $n$ になる $2$ 個 $1$ 組で存在している。
よって、$\sqrt{n}$ の小さい方を探し、見つけたときについでに相方も記録するだけでよい。

例えば、$20$ の約数を列挙するとき、$\sqrt{20}\fallingdotseq4.47$ 以下だけ探せばよい。
その探索から $1,2,4$ が見つかり、$20$ をそれらで割って $20,10,5$ が見つかる。

vector<long long> divisors;

for (long long i=1; i*i<=n; i++) {
  if (n%i) continue; 
  divisors.emplace_back(i);
  if (i*i!=n) divisors.emplace_back(n/i);
}

$n$ が平方数のときの扱いに注意。
例えば $n=9$ のときに $3$ をダブって記録しないように気をつけなければならない。

最大公約数（C問題相当）

$a$ と $b$ の約数として共通しているもののうち、最大のものが最大公約数である。
例えば、以下のようなもの。

$24$ の正の約数は、$1,2,3,4,6,8,12,24$ である。
$42$ の正の約数は、$1,2,3,6,7,14,21,42$ である。
よって、共通する $1,2,3,6$ が正の公約数で、そのうち最大である $6$ が最大公約数。

最大公約数を求めたいとき、それぞれの約数を頑張って全部列挙して探す必要はない。
C++23環境なら標準ライブラリに存在し、以下のように書くだけで求まる。

int g = gcd(a,b);

ユークリッドの互除法（C問題相当）

$2$ 数の最大公約数を高速に求めるアルゴリズムが存在する。
上で述べた gcd() の中身も、環境によるが、おそらくこれ。

最大公約数について、以下のような法則がある。

$a$ と $b$ が既知であり、その最大公約数 $g$ が未知であるとする。
このとき、まず $a$ を $b$ で割った余りを $c$ とする。
$b$ と $c$ の最大公約数を求めると、実はそれが全く同じ $g$ となる。

これを繰り返すことで、最大公約数が高速に求まる。
例えば、$403$ と $299$ の最大公約数を求めたい場合、以下のような手順となる。

$403$ を $299$ で割った余りは $104$ である。
よって、$299$ と $104$ の最大公約数を求めれば、それが知りたい値である。
$299$ を $104$ で割った余りは $91$ である。
よって、$104$ と $91$ の最大公約数を求めれば、それが知りたい値である。
$104$ を $91$ で割った余りは $13$ である。
よって、$91$ と $13$ の最大公約数を求めれば、それが知りたい値である。
$91$ を $13$ で割った余りは $0$ である。
割り切れたので、これらの最大公約数は $13$ である。
よって、元々求めたかった $403$ と $299$ の最大公約数も $13$ である。

実装は再帰関数によって行うことができ、一例は以下。
標準ライブラリがあるのに自分で実装する必要があるのかという話もあるが、再帰の練習にはピッタリ。

long long my_gcd(long long a, long long b) {
  if(b==0) return a;
  return my_gcd(b, a%b);
}

また、このアルゴリズムには全く別方向への応用がある。
詳しくは「拡張ユークリッドの互除法」の記事参照。

最小公倍数（C問題相当）

$a$ と $b$ の正の倍数として共通しているもののうち、最小のものが最小公倍数である。
例えば、以下のようなもの。

$6$ の正の倍数は、$6,12,18,24,30,36,42,48,54,60,\dots$ である。
$8$ の正の倍数は、$8,16,24,32,40,48,56,64,\dots$ である。
よって、共通する $24,48,72,\dots$ が正の公倍数で、そのうち最小である $24$ が最小公倍数。

最小公倍数を求めたいとき、それぞれの倍数を頑張って列挙して探す必要はない。
C++23環境なら標準ライブラリに存在し、以下のように書くだけで求まる。

long long l = lcm(a,b);

あるいは、以下のように求めてもよい。
最大公約数と最小公倍数の積が元の $2$ 数の積に一致することを利用している。
先に掛け算をするとオーバーフローの危険があるので注意。

long long g = gcd(a,b);
long long l = a/g*b;

約数列挙その3（D問題相当）

正整数 $n$ の素因数分解が $n=p_1^{e_1}\times p_2^{e_2}\times p_3^{e_3}\times\dots\times p_k^{e_k}$ だったとする。
このとき、$n$ の正の約数は、それぞれの指数を $n$ での指数以下の数にしたものとして表せる。

例えば、$288=2^5\times 3^2$ の正の約数は以下の $18$ 個。

	$2^0$	$2^1$	$2^2$	$2^3$	$2^4$	$2^5$
$3^0$	$1$	$2$	$4$	$8$	$16$	$32$
$3^1$	$3$	$6$	$12$	$24$	$48$	$96$
$3^2$	$9$	$18$	$36$	$72$	$144$	$288$

素因数が $3$ 種類以上あると表が $3$ 次元以上になるが、考え方は同様。
これを利用して、素因数分解の結果から約数列挙を行うことができる。

prime_factorization は素因数分解して {素因数,指数} の配列にする関数。
詳しくは「素因数分解」の記事参照。

vector<long long> divisors(long long n, bool sorted = false) {
  assert(n>0);
  vector<pair<long long,int>> primes = prime_factorization(n);
  vector<long long> result(1,1);
  for (auto [p,e] : primes) {
    int l = ssize(result);
    result.resize(l*(e+1),0);
    for (int i=0; i<l*e; i++) {
      result[i+l] = result[i]*p;
    }
  }
  if (sorted) sort(result.begin(),result.end());
  return result;
}

$1$ つの整数の約数列挙をするだけなら、基本的にはただ複雑なことをしているだけである。
しかし、素因数が小さい整数ばかりの場合には、素因数分解が素早く終わるため、この方法が有効。
また、エラトステネスの篩を用いる素因数分解と組み合わせると、大量の処理が高速に処理できる。

約数の個数（D問題相当）

$n$ の約数がいくつあるか、を求めたいことがある。
これは、前項目の計算方法を考えればわかりやすい。

正整数 $n$ の素因数分解が $n=p_1^{e_1}\times p_2^{e_2}\times p_3^{e_3}\times\dots\times p_k^{e_k}$ だったとする。
正の約数の個数は、$(e_1+1)\times (e_2+1)\times (e_3+1)\times\dots\times (e_k+1)$ である。
正負問わず約数を数える場合は、その $2$ 倍。

約数の総和（D問題相当）

$n$ の正の約数を全部足すといくつか、を求めたいことがある。
これも、前項目の計算方法を考えればわかりやすい。

正整数 $n$ の素因数分解が $n=p_1^{e_1}\times p_2^{e_2}\times p_3^{e_3}\times\dots\times p_k^{e_k}$ だったとする。
正の約数の総和は、$(1+p_1^1+p_1^2+\dots +p_1^{e_1})\times (1+p_2^1+\dots +p_2^{e_2})\times\dots\times (1+\dots +p_k^{e_k})$ となる。
なぜなら、これを展開した結果が、文字通りの正の約数の総和の式になるからである。

トーシェント関数（E問題相当）

$2$ つの整数 $a$ と $b$ の最大公約数が $1$ であることを、「$a$ と $b$ は互いに素である」という。
$1$ 以上 $n$ 以下の整数のうち、$n$ と互いに素であるものがいくつあるか、を求めたいことがある。
これはトーシェント関数 $\varphi(n)$ と呼ばれる。

例えば、$10$ 以下の数のうち $10$ と互いに素であるものは $1,3,7,9$ の $4$ つある。
よって、$\varphi(10)=4$ である。

正整数 $n$ の素因数分解が $n=p_1^{e_1}\times p_2^{e_2}\times p_3^{e_3}\times\dots\times p_k^{e_k}$ だったとする。
すると、$\varphi(n)=n\times\frac{p_1-1}{p_1}\times\frac{p_2-1}{p_2}\times\frac{p_3-1}{p_3}\times\dots\times\frac{p_k-1}{p_k}$ となる。

各々の分数は割り切れないので、$\times\frac{p_1-1}{p_1}$ は $\div p_1\times(p_1-1)$ で処理すること。

これが何に役立つかというと、剰余類環との組み合わせである。
$ax$ を $n$ で割った余りが $b$ であるとき、$x$ を $n$ で割った余りを求めたいことがある。
$n$ が素数で $a$ と $n$ が互いに素であれば、答えは $b\times a^{n-2}$ を $n$ で割った余りとなる。
これは、「剰余類環」の記事を参照。

では、$n$ が素数でなかったらどうするか？

答えは、$a$ が $n$ と互いに素である場合には一意に求められ、$b\times a^{\varphi(n)-1}$ を $n$ で割った余りとなる。
例えば $3x$ を $10$ で割った余りが $4$ である場合、$x$ を $10$ で割った余りを求めたいとする。
この場合は、$\varphi(10)=4$ なので、$4\times3^{4-1}=108$ を $10$ で割った余りの $8$ である。

$a$ が $n$ と互いに素でなかった場合は、$a,b,n$ の全てを $a$ と $n$ の最大公約数で割って考える。
$4x$ を $10$ で割った余りが $6$ である場合は、$2x$ を $5$ で割った余りが $3$ であるとして解く。
これは、$10$ で割った余りとしては一意に定まらない。
$4x$ を $10$ で割った余りが $7$ である場合は、$7$ を $2$ で割りきれないため、そのような数は存在しない。

注意点

特になし。