階乗の割り算の話

こんな問題がありました。
{\displaystyle\frac{a!}{b!*c!}(1<=a,b,c<=1000)}
なんか割り切れる問題みたいです。さらに結果はそれなり（long longで桁あふれしない）みたいです。

これをプログラム（C++）で計算するとa!の時点で桁あふれする予感がします。
またa!/b! a!/c!でも計算結果が桁あふれするかもしれません。
どうやら同時に計算しなきゃいけないみたいです。

結果から言うと素因数分解をすればいいですね。すべての変数は1000以下のためメモリも大丈夫そうです。
素因数p1で何度割ることができるかををa_p1 b_p1 c_p1で表すと答えの素因数は
{\displaystyle\ p1^{a_p1-b_p1-c_p1}}
となるのでa以下の素因数すべてで行えばいいのです。

最後に素因数をすべて掛け合わせることで結果が求められますね。

■

この記事は

FUN Advent Calendar 2016

の22日目の記事になります。

 

www.adventar.org

ついでに初投稿なので、見づらい部分があると思います。

記事

/*----- なぜキョウプロをやらないのか -----*/

数ある記事がとびとびに書かれてきた「FUN Advent Calendar 2016」ですが、専門的な話はできないので競プロについて書きます。

 

そもそも「競プロってなんなん。」という人がいると思うので説明すると、決められたテーマがあってそれに合うソフトウェア作ったり、問題が与えられるのでルールに沿った中で高得点目指したり、入力が与えられるので完璧な出力を返したりするやつです。

 

今回は完璧な出力を返す競プロについて書きます。

/*----- 問題の例 -----*/

例えばこんな問題

時計 | プログラミング入門 | Aizu Online Judge

入力 

秒数が与えられる

出力

時：分：秒に直せ

 

という問題です。

簡単ですね。

回答例を載せておきます。

gist.github.com

 

もっと効率的なやり方があると思ったあなたは競プロに向いています。ぜひやりましょう。

 

/*----- キョウプロのデメリット -----*/

競プロをやりすぎると体に悪影響を及ぼします。

  • 回答が分からなくて寝不足になります。
  • どこが間違っているかわからなくてストレスになります。
  • 英語の問題文を見ただけで吐き気を催す人がいます。
  • 正答例をみたときに著者のコメントに「簡単」とか「やるだけ」と書いてあります。
  • 時間制限のコンテストをやる前はもれなく体調を崩します。
  • そして上記には中毒性があります。

これらの悪影響は日常生活を著しく阻害し、快適なライフが送れなくなります。

 

/*----- キョウプロのメリット -----*/

競プロをやると絶大な効果が得られます。（個人差があります）

  • 問題に正解（通称：AC）すると一時的に気分が楽になります。
  • 次の問題にとりかかろうとする意欲がわきます。
  • 高揚感と自己実現感が高まり、物事をプラスに見れます。
  • ガッツポーズをすると単位が出ます。

デメリットと比べてやりたい人はやると良いでしょう。

 

/*----- 本題 -----*/

ここまで読んできて、「まったく面白さが理解できないよ」という方がいらっしゃるかもしれません。

しかし、これは私の文章が悪いのです。

/*

競プロは面白くないのでは->ホントは文章が悪い->競プロは面白い

*/

理解いただけたでしょうか。

 

競プロは楽しみながらプログラミング技術を鍛えることができます。（個人差があります）ライブラリの使い方や、特殊なギミックを用いたwebコンテンツも触ってみるに越したことはないです。しかしながら、アルゴリズムを用いてプログラムをかき、高速な計算をさせるというのはどの言語でも共通の目標ではないでしょうか。

 

先程の問題がたくさんあるAizuOnlineJudgeやほぼ毎週末にやっているAtCoderのコンテストに参加してみてアルゴリズムの奥深さを学んでもよいのではないでしょうか。

 

P.S.1　この記事には主観的な内容が多く含まれています。

P.S.2　著者は今日誕生日です。祝ってみるのもいかがでしょうか。

P.S.3　競プロを始めたことで起こる不具合や寝不足には一切の責任を負いません。何卒よろしくお願いします。