【C#】AtCoder Beginner Contest180 C - Cream puff をC#で解いてみた【AtCoder】
※この解答は個人の見解の為、参考程度にご覧ください。
〇問題文
N 個のシュークリームがあります。
シュークリームを分割することなく平等に分けることができるような人数としてあり得るものを全て求めてください。
簡単に言うと素因数分解しろって問題。
めっちゃ簡単やんけ!と思いきや、安直にループで全値走査するとでかい値のテストケースの時にタイムアウトを起こす…。
そこはほら、競技プログラミングだからね。ちゃんと効率のいいアルゴリズムを使おうね。
〇解答例
static void Main(string[] args) { //大きな値のテストケースにそなえ、Long型にする var N = long.Parse(Console.ReadLine()); List<long> ans = new List<long>(); //約数列挙というアルゴリズムを使う //ある値が割り切れる(約数である)のならば、その累乗した値も約数である //for文の条件で、i * iを採用したのは上記の約数列挙の理屈に基づいたもの //Nに値が近づくまで走査を繰り返す //この手法は普通のループに比べて計算量が少なくて済む for(long i = 1; i*i <= N; i++) { //Nがiで割り切れる場合、リストに値を追加する(約数である) if(N % i == 0) { ans.Add(i); //さらにiがN÷iの値と同一ではない時は、N÷iの値をリストに追加する //ex)N=720、i=2のとき、N÷i=360となるのでリストに追加する //Nと昇順と降順からそれぞれ計算を進めていくイメージ if(i != N/i) { ans.Add(N / i); } } } //約数のリストアップが終わったら昇順にソートしてあげる ans.Sort(); //String.Joimクラスを使ってコレクションの要素を\n(改行)でくっつけ、出力する Console.WriteLine(string.Join("\n", ans)); }