素因数分解を用いた約数の個数の求め方

求め方

素因数分解を用いた約数の個数の求め方を解説します。

約数の個数を求めるために、どのように素因数分解を用いるのかというところですが、以下のことを利用します。

自然数Nを素因数分解した結果が、$N = p^aq^br^c ...$のとき、Nの正の約数の個数は$(a + 1)(b + 1)(c + 1)...$ 個である。

なぜ上記のことが成り立つのかということですが、まず自然数Nは素因数pをa個,素因数qをb個,...もつ数と言えます。
なので、自然数Nの約数は、素因数pをa個以下、素因数qをb個以下持つ数であるということも言えます。
これらの組み合わせの数は、pの指数は$(a+1)$通り、qの指数は$(b+1)$通り、...となるので、これらをかけると約数の個数が求められます。

例として、60の約数の個数を求めるためにこの方法を使ってみましょう。
$60 = 2^2 \times 3 \times 5$ というように60は素因数分解できます。
素因数2,3,5の指数はそれぞれ2,1,1なので、約数の個数は$(2 + 1)(1 + 1)(1 + 1) = 12$個と求められます。
実際に、60の約数の個数は12個です。(1,2,3,4,5,6,10,12,15,20,30,60の12個)

ここまでの内容でわかることは、素因数分解した結果がわかっていれば、約数の個数もわかるということです。。
ここからは、このことを使った問題の解き方について紹介していきます。

例題1

$N!$の約数の個数を数えるのは大変ですが、$N!$を素因数分解した結果は簡単に求められるので、それをつかって約数の個数を計算します。

#include <bits/stdc++.h>
using namespace std; using ll = long long;

signed main(void){
  int n;
  cin >> n;
  vector<int> prime(1001, 0); //素因数の個数を記録する配列
  for(int i = 2; i <= n; i++){
    int x = i;
    for(int j = 2; j * j <= n; j++){ //xを素因数分解する
      while(x % j == 0){ //割り切れるなら
        prime[j]++; //個数を加算
        x /= j;
      }
    }
    if(x != 1) prime[x]++;
  }
  
  ll ans = 1;
  for(int i = 1; i <= 1000; i++){
    cerr << prime[i] << endl;
    ans *= (prime[i] + 1);
    ans %= 1000000007;
  }
  cout << ans << endl;
}

例題2

この問題では、約数の個数はわかっているので、約数の個数を活かして数を求めます。

約数が9個の数はどのように素因数分解されるかを考えてみます。
約数が9個ということは、言い換えると $N = p^aq^b$ と素因数分解されるとき、$(a + 1)(b + 1) = 9$　であるということです。(9は3つの2以上の整数の積では表せない。)
$(a + 1)(b + 1) = 9$を満たす$(a + 1)$と$(b+1)$の組み合わせを考えてみると、
$a + 1 = 3, b + 1 = 3$
$a + 1 = 9, b + 1 = 1$
$a + 1 = 1, b + 1 = 9$
の3つだとわかります。

このことから、Nを素因数分解したときの結果が次のように表せるとき、約数が9個であるといえます。
$N = p^2q^2, p^8, q^8$
p^8とq^8は同じようなことを意味しているので、$N = p^2q^2, p^8$　と表せると約数が9個といえます。

ここまでのことがわかれば、全探索で答えが求められます。

#include <bits/stdc++.h>
using namespace std; using ll = long long; using ld = long double;

signed main(void){
  ll n;
  cin >> n;
  
  vector<ll> prime; //素数を記録する配列
  prime.push_back(2);
  for(ll i = 3; i < 1000000; i++){　//素数を配列に追加
    bool ok = true; //素数かどうか
    for(ll j = 2; j * j <= i; j++){
      if(i % j == 0){ //割り切れるか判定
        ok = false;
        break;
      }
    }
    if(ok) prime.push_back(i);
  }
  
  ll ans = 0;
  //p^2q^2について
  for(ll p = 0; p < prime.size(); p++){ //(p < q)
    if(prime[p] > 1500) break; //prime[p] > 1500 ならp^2q^2 > N
    for(ll q = p + 1; q < prime.size(); q++){
      ll num = prime[p] * prime[p] * prime[q] * prime[q];
      //p^2q^2で表せる数を計算
      
      if(num <= n){ //N以下なら
        ans++;
      }
      else break;
    }
  }
  //p^8について
  for(ll i = 0; i < prime.size(); i++){
    if(prime[i] > 40) break;
    ll num = 1;
    for(int j = 0; j < 8; j++) num *= prime[i]; //p^8を計算
    if(num <= n){
      ans++;
    }
  }
  cout << ans << endl;
}