D - 756
はじめに
競技プログラミング、AtCoder Beginner Contest 114
D - 756
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
整数Nが与えられます。 N!(=1×2×...×N)の約数のうち、七五数 は何個あるでしょうか？ ここで、七五数とは約数をちょうど75個持つ正の整数です。
注記
正の整数Aが正の整数Bを割り切るとき、AをBの約数 といいます。 例えば、6の約数は1,2,3,6の4個です。
制約
・1≤N≤100 ・Nは整数である。
入力
入力は以下の形式で標準入力から与えられる。 N
出力
N!の約数であるような七五数の個数を出力せよ。
解き方
こちらの解き方を参考にしています。 www.youtube.com atcoder.jp
N!の約数のうち、約数をちょうど75個もつものを考えます。
約数の個数
約数の個数は
数を素因数分解して出てくる数の組み合わせの数です。
例えば、
12を例にして考えてみます。
12を素因数分解すると以下のようになります。
12＝22×3
ここから約数の個数は
2が「0～2」の(2+1)パターン×3が「0か1」の(1+1)パターン＝6パターン
となります。
全部のパターンを書き出すと以下のようになります。
20×30=1
21×30=2
22×30=4
21×31=6
22×31=12
20×31=3
ここから、
少し視点を変えて
約数の個数が75個、
つまり75パターンの組み合わせを持つことについて考えます。
先程、
12の約数を考えたときは
素因数分解した数の項を掛け合わせて
以下のようにパターンを出しました。
(2+1)×(1+1)＝6パターン
ここから、
任意の数をｐ、ｑと置くと
p3×q2という形になるものは
全て約数を6つもつことになります。
そして、よく見てみると
各数字の項になっている
3、2という数字も
また6の約数であることに気づきます。
ここから
約数を
75個パターン持つような組み合わせは
以下のように出すことができます。
75＝3×52=(74+1)=(2+1)×(24+1)=(14+1)×(4+1)=(2+1)×(4+1)×(4+1)
つまり、
以下の形になるものは約数を75個持つと言えます。
適当な数字をp,q,rと置く
p74
p2×q24
p14×q4
p2×q4×r4
75個約数を持つ数字が
どのような形になるのかが分かったので
N!を素因数分解して
それぞれの数がいくつ含まれているのかを出し
上のかたちにできる個数を考えます。
例えば、N＝10のとき
10!=28×35×527
これを記号で置き換えると
p8×q5×52×7
となり、
上で挙げた約数が75になるパターンの中で
p2×q4×r4
のかたちのみが作れるので
1が答えになります。
全体のコード
using System;
using System.Linq;
using System.Collections.Generic;
class Dmondai
{
static void Main()
{
var N = Int32.Parse(Console.ReadLine());
//素因数分解の結果を保存
//indexを各素数とする（ただし素数のみでするのは面倒なので、分けずに1～100）
//Nは最大で100なので100以上の素数がくる可能性はない
var array = new int[100];
//1ではどんな数も必ず割れるのでindex=0には1を入れる（一つずつずれます）
array[0] = 1;
//配列の初期化、index=1を除くすべてに0を入れる
for (int i = 1; i < 100; ++i) array[i] = 0;
//素因数分解していく
//N!の各数字
for (int i = 2; i <= N; ++i)
{
//iを操作すると外側のループがおかしくなるので
//別の変数に保存して使用
var num = i;
//iを素因数分解する
//2から順番に各素数で割る（ただし面倒なのでループ自体は素数を区別しない）
for (int k = 2; k <= i; ++k)
{
if (num < k) break;
//割れるだけ割る
while (num % k == 0)
{
array[k - 1]++;
num /= k;
}
}
}
//75個の約数を持つ形に当てはまる数を保存するリスト
var list = new List<double>();
//75個の約数をもつかたちに当てはまるかどうかを見ていく
for (int i = 0; i < array.Count(); ++i)
{
if (array[i] == 0) continue;
//74
if (74 <= array[i])
{
var n = Math.Pow(i + 1, 74);
if (!list.Contains(n)) list.Add(n);
}
for (int j = 0; j < array.Count(); ++j)
{
if ((array[j] == 0) || (j == i)) continue;
//4,14
if (4 <= array[i] && 14 <= array[j])
{
var n = (Math.Pow(i + 1, 4) + Math.Pow(j + 1, 14));
if (!list.Contains(n)) list.Add(n);
}
//2,24
if (2 <= array[i] && 24 <= array[j])
{
var n = (Math.Pow(i + 1, 2) + Math.Pow(j + 1, 24));
if (!list.Contains(n)) list.Add(n);
}
for (int k = 0; k < array.Count(); ++k)
{
if ((array[k] == 0) || (k == i) || (k == j)) continue;
//2,4,4
if (2 <= array[i] && 4 <= array[j] && 4 <= array[k])
{
var n = (Math.Pow(i + 1, 2) + Math.Pow(j + 1, 4) + Math.Pow(k + 1, 4));
if (!list.Contains(n)) list.Add(n);
}
}
}
}
Console.WriteLine(list.Count());
}
}
