OMC水までの問題に使う知識まとめ
はじめに
こんにちは。OMC水のミカン小僧です。今回は、OMCで水くらいまでに使う知識やテクニックをまとめてみました。皆様の参考になれば幸いです。
注意
0．筆者の数学力が著しく低いので、この記事はまだまだ不十分であると思っています。そのため忌憚ない感想やご指摘をお待ちしております。
1．この記事は大体OMC水diffくらいまでの問題を解けるようになることを想定して作られています。それ以上は筆者の手には負えかねますのでご了承ください。
2．この記事にはかなり基本的なことも含まれます。難易度を星の数で表示するので、自分に合った難易度のものを選んでください。
3．この記事のコンセプト(知識とそれを使うOMCの問題を紹介する)上、OMCの問題のネタバレが含まれる可能性があります。あらかじめご了承の上お読みください。
この記事の使い方
あまり満足する説明を載せられなかったので、この記事で紹介した知識を自分で調べてみて、その後問題に挑戦してみてください。以下、調べるのにおすすめのサイトを紹介します。
高校数学の美しい物語 筆者のおすすめです。なんといっても記事が多い。あと分かりやすい。
KIT数学ナビゲーション 分野ごとにまとまっていて調べやすいです。簡潔にまとめてあるので調べたいことがすぐにわかる半面、慣れてない人にとっては難しく感じるかもしれません。
他、Mathlogなどで記事を探すのもよいかもしれません。特に競技数学独自のテクニック(主客転倒など)については、ここからしか得られない情報も多いです。
もう一つ紹介させていただきたいのは、Noppi_kun様のOMCwiki(非公式)というサイトです。競技数学のテクニックが書かれていて、かなり役に立ちます。
難易度表示について
★ 灰
★★ 茶
★★★ 緑
★★★★ 水下位
★★★★★ 水中位～上位
A
文字の消去 ★
基本的なことですが、盲点となりうるので。(x、yの単純な式) = (定数)みたいな時は、まずyを消去しましょう。例えば、$${x+y=2}$$みたいな式の時は、$${y=2-x}$$みたいに変形して、変数を一個にできます。でも複雑な式になるとドツボにはまるのでやめようね。
・使う問題
いっぱい
一次方程式 ★
文章題とかでもよく見るやつですね。やるだけなので特には述べません。
・使う問題
いっぱい
シンプルな不等式 ★
「シンプルな」というのは出てくる文字の種類がせいぜい2種くらいまでという意味です。大体普通の方程式と同じように処理できますが、負の数をかけたり割ったりするときは不等号の向きが逆になることに注意しましょう。
・使う問題
いっぱい
二次方程式 ★
分野に限らず色んなところで使う必須知識。$${x⁴+2x²+1=0}$$みたいに文字を置き換えると出てくるパターンも多いです。二次方程式$${ax^2+bx+c}$$の解の公式は
$$
x = \frac{ -b \pm \sqrt{b^2 - 4ac}}{2a}
$$
・使う問題
OMC066C
連立方程式 ★
連立方程式には様々なパターンがありますが、基本は一文字消去することです。これだけは覚えておいてほしい。
・使う問題
OMC063A
因数分解 ★
超超超超超超重要です。色んな記事を読んで勉強してください。受験数学の参考書をやることもお勧めします。
・使う問題
OMC049B
OMC063C(N)
絶対値 ★
xが非負の時xを、負の時-xを返す関数です。絶対値を使った方程式は、場合分けを頑張れば解けます。
・使う問題
OMC065C
判別式 ★★
二次方程式に解があるかどうか判定するもの。二次方程式$${ax^2+bx+c}$$において、$${D=b^2-4ac}$$とおくと、$${D>0}$$のときこの二次方程式は二つの実数解を持ち、$${D=0}$$のときこの二次方程式は一つの実数解を持ち、$${D<0}$$のときは実数解を持たない。
・使う問題
OMCB015F
平方完成 ★★
最大値・最小値を求める問題の時2番目に使うイメージ。問題をいっぱい解いて速くできるようにしましょう。
・使う問題
OMC035B
OMC045A
OMCB015B
相加相乗平均 ★★
詳しくは高校数学の美しい物語の記事を参照。
平方完成の項で「最大値・最小値を求める問題の時2番目に使うイメージ」と言っていましたが、その1番目がこれです。分野関係なくめっちゃ見ます。最小値を求める問題が出てきたらとりあえず確認しましょう。正の実数でしか成り立たないことに注意してください。発展的なテクニックはこちらの記事などがよいと思います。
・使う問題
OMC023B
OMC041B(N)
OMC043A(G)
OMC047B
OMC179D
OMC183E
部分分数分解 ★★
詳しくは高校数学の美しい物語の記事を参照。Nでもよく見ます。
$${\frac{定数}{二次式}}$$の時は99.99%これ(偏見)
・使う問題
OMC033A
OMC072E
床関数・天井関数 ★★
$${\lfloor n \rfloor}$$は床関数といい、nより小さい最大の整数を、
$${\lceil n \rceil}$$は天井関数といい、nより大きい最小の整数を表します。
この記事などに性質がまとめられているので、読んでみるとよいでしょう。
・使う問題
OMC049D
係数比較 ★★★
時には展開して係数を調べることも有効です。
・使う問題
OMC070E
係数の和 ★★★
1を代入すれば終わり。1個飛びの場合は‐1を代入するとよいです。
・使う問題
OMC058C
解と係数の関係 ★★★
星3つにしましたが超重要です。少なくとも2次方程式の場合は暗記しておいてほしいです。なぜそのようになるかを理解して、3次以降にも応用できれば○。こちらの記事も参照。
・使う問題
OMC037A
対称式 ★★★
高校数学の美しい物語の記事を参照。対称式でまとめると見通しがよくなることが時々あります。
・使う問題
OMC035C
OMC037A
OMC066E
コーシー・シュワルツの不等式 ★★★
この記事などが参考になります。$${(A^2+B^2)(C^2+D^2)\geq (A×C+B×D)^2}$$という形をよく見るので、この形だけでも覚えておくとよいかもしれません。
・使う問題
OMC039C(G)
OMC072D(G)
複素数 ★★★
複素数とは、$${i=\sqrt{-1}}$$を満たす数$${i}$$を用いて$${a+bi}$$と表される数のことを指します。本来なら$${i}$$のような数は存在しえないはずなのですが、あるとして話を進めるわけです。OMCで出るときは、共役な複素数の性質を使うことがあります。
・使う問題
OMC045A
漸化式(A) ★★★
A分野の時は、漸化式から一般項を求める必要があることがあります。このことを漸化式を解くといいます。こちらの記事やこちらの記事などで解き方がまとめられていますが、とにかく演習することが大事だと思っているので、一通り解き方を覚えたら漸化式ガチャなどでどんどん解きましょう。
・使う問題
微分積分 ★★★★
OMCは数オリとは違うのでこういうのもガッツリ出ます。(物議を醸すこともありますが…)
とりあえず多項式の微分積分ができれば大丈夫だと思います。説明はめんどくさいので各自で勉強してください。
・使う問題
OMC043C(G)
OMC183E
C
数え上げ ★
時には、素直に数え上げするのが一番早い、という問題もあります。数え上げ力を鍛えるとこういう問題でかなり有利になれます。
・使う問題
OMC070C
OMC072C
OMC075B(N)
OMC076A
余事象 ★
(全体の集合)-(条件を満たさない部分)で条件を満たすものが求められるよ、というものです。例えば、1000000000までの数で3で割り切れないものは何個あるか？という問題では3の倍数を数えてそれを1000000000から引いたほうが簡単に求められます。
・使う問題
OMC037B
OMC061B
順列と組み合わせ ★
これを覚えてないという人は今すぐ覚えましょう。この記事などがおすすめです。
・使う問題
OMC075A
同じものを含む順列 ★★
simasimaという文字列を並び替える方法は何通りあるか？といった問題です。受験の月の記事などが参考になります。早めに覚えておいてほしい公式の一つです。
・使う問題
OMC065A
OMCB019A
重複組み合わせ ★★
8個のチョコをO君、M君、C君に配る方法は何通りあるかという問題を考えてみましょう。ただし、一つも貰えない人がいてもよいものとします。
このような問題は、「仕切り」を考えることで解くことができます。この問題の場合は、チョコをO、仕切りをIとすると、Oを8個、Iを2個並べた時に、左からO君、M君、C君の取り分とすればよいです。例えば、
OOIOOOIOOO
は、O君が2個、M君が3個、C君が3個チョコをもらうことと対応します。Oを8個、Iを2個並べる方法は$${{}_{8+2}C_{2}=45}$$通りなので、答えは45通りとなります。
・使う問題
OMC065B
OMC075E
手動DP ★★
結構強力な道具。計算がめんどくさいですが低難易度のCはこれで倒せることが多いです。前に書いた記事で解説しているので是非ご覧ください。
・使う問題
OMC021C
OMC041C
OMC043B
OMC075C
包除原理 ★★
余事象の発展編です。この記事やこのブログなどが分かりやすかったので、ぜひご覧ください。
・使う問題
OMC045C
隣同士のものに条件がつく問題 ★★
隣の頂点の色が異なるように多角形を塗り分けるなどの問題です。やってみたらできたというような問題が多いので難易度は全体的に低め。コツとしては、制約が強いものから順に埋めていくこと(「隣り合ったマスの目の和が～以下」といった問題では、一番大きい数から埋めましょう)。手動DPが刺さることもしばしばあります。
・使う問題
OMC027B
OMC039B
OMC052C
OMC066A
フィボナッチ数列 ★★★
$${a_1=1, a_2=1, a_{n+2}=a_{n+1}+a_n}$$という漸化式で表される数式をフィボナッチ数列といいます。つまり$${1, 1, 2, 3, 5, 8, 13, 21\dots}$$と続いていくわけです。
この数列は色んな所で出てくるので、あらかじめ自分でフィボナッチ数列の表を作っておくと、計算がちょっと早くなると思います。
・使う問題
OMC021C
OMC043B
主客転倒 ★★★
こちらのMetachick様の記事がとても参考になります。他にもMathlogなどに素晴らしい記事が沢山あるので、いろいろ自分で調べてみるとよいと思います。
・使う問題
OMC075D
OMCE007A
各桁ごとに考えるやつ ★★★
いわゆる主客転倒の一種です。「～な数の総和を求めろ」みたいな問題に使うことが多いです。
・使う問題
OMC029A
OMCB015C
サイクル ★★★
こんな問題を考えてみましょう。
$${1}$$から$${a}$$、$${2}$$から$${b}$$、$${3}$$から$${c}$$、$${4}$$から$${d}$$(ただし$${1\leq a,b,c,d \leq 4}$$)を結ぶあみだくじがあります。このあみだくじを$${3}$$個つなげた時、初めて$${1}$$から$${1}$$、$${2}$$から$${2}$$、$${3}$$から$${3}$$、$${4}$$から$${4}$$に戻りました。この時、$${(a,b,c,d)}$$としてあり得る組はいくつありますか。
この問題を解くとき、まず$${a}$$に注目してみましょう。$${a=1}$$のとき、常に1なので3回目時点でも1になります。このようなパターンを要素1のサイクルとします。次に、$${a\neq 1}$$のときを考えます。このとき、あり得るのはちょうど3回で1に戻ってくるパターンのみです。このようなパターンを要素3のサイクルとします。
ここで、元の問題に戻ってみます。「このあみだくじを$${3}$$個つなげた時、初めて」元に戻っているので、要素3のサイクルが必ずなければいけません。あとはこのようなものの数を数えれば答えは8であるとわかります。
一般に、あみだくじを$${N}$$個つなげた時に元に戻った時、すべてのサイクルの要素の公倍数が$${N}$$になります。
・使う問題
OMC061D
漸化式(C) ★★★
手動DPを少し前に紹介しましたが、実質的には漸化式のことを指します。慣れてくると、手動DPよりはるかに楽に解けるのでおすすめです。小さいところから考えて、一つずつ大きくするとどうなるのか考えることがコツです。
・使う問題
OMC181E
分割数 ★★★★
分割数とは、ある数を1以上の数の和で表す方法の数のことです。5を例とすると、
5
1+4
2+3
1+1+3
1+2+2
1+1+1+2
1+1+1+1+1
の7個あるわけですね。ヤング図形というものと一対一対応していて、これを利用すると解ける問題が時々あります。詳しくは高校数学の美しい物語の記事をご覧ください。
・使う問題
OMC049F
積の和 ★★★★
簡単な積に帰着できることがままあります。多項式で表せないか考えてみましょう。
・使う問題
OMC039A(A)
OMC045C
偶奇の場合分け ★★★★
本来ならNに入れるべきかもしれませんが、どちらかというとCに近い気がしました。グラフと組み合わせて使うパターンをよく見ます。
・使う問題
OMC029D
期待値の平均 ★★★★
ちょっと発展的なテクニックです。たとえば、1から100までの数から相異なる2つの数を選んでその2つを足し合わせたものの総和を求めるという問題を考えましょう。
ここで、1から100までの数を選んだ時、選ばれる数の平均は
$$
\frac{1+2+\dots +99+100}{100}=\frac{101}{2}
$$
です。
よって、2つ選んだ時の和の平均は101となります。1から100までの数から相異なる2つの数を選ぶ方法は$${{}_{100} C_2=4950}$$通りあるので、求める答えは$${101\times 4950=499950}$$です。
この問題では平均を使うことのすごさがあまり伝えられなかったかもしれませんが、このテクニックをうまく使うとすごく楽に問題が解けることが時々あります。
・使う問題
OMC047C
OMC070B
G
三平方の定理 ★
すべての基礎。図において、
$${a^2+b^2=c^2}$$が成り立つというものです。
・使う問題
OMC068C
多角形の内角・外角 ★
n角形の内角の和は$${180(n-2)}$$。また、多角形の外角の和は常に360度。
・使う問題
OMC029B
OMC049A
OMCB015D
円周角の定理とその逆 ★
これは絶対に身につけておきましょう。詳しくはこちら。直角のときはタレスの定理というのが成り立つので、これも覚えておきましょう。。
・使う問題
OMC029C
OMC023D
OMC043A
OMC047C(C)
OMC045F
三角不等式 ★
三角形の辺を$${a,b,c}$$とした時、$${a+b>c}$$が成り立つという不等式。図を描いてみると一瞬で納得できると思います。三角形の成立条件を求めるときによく使います。
・使う問題
OMC037B
対角線 ★
対角線とは、多角形の隣り合わない2頂点を結んだ線分のことを指します。$${n}$$角形対角線の個数を求める公式は
$$
\frac{n(n-3)}{2}
$$
です。覚えておくと時々役に立ちます。
・使う問題
OMC058A
OMC058B
相似 ★★
むっっっちゃくちゃ重要です。相似条件は
① 2辺の比とその間の角が等しい
② 2角が等しい
の2つありますが、②のほうが圧倒的に出ます。とにかく問題をたくさん解いて相似を見つける目を養いましょう(と偉そうなことを言っていますが私は相似が大の苦手です)。
・使う問題
OMC072A
OMC078B
二等分線と辺の比 ★★
この記事に色んな公式がまとめられています。特に重要なのは最初の公式です。これは絶対に覚えておきましょう。これを拡張したものがスチュワートの定理です。
・使う問題
三角形の面積の求め方 ★★
別途記事を書きます
・使う問題
OMC076D
円の接線 ★★
直線$${BD}$$と直線$${CD}$$が点$${A}$$を中心とする円に接するとき、
$${\angle{ABD} = \angle{ACD}=90\degree}$$
$${BD=CD}$$
が成り立ちます。
方べきの定理 ★★★
図1において$${BC\times BD=BE\times BF}$$が成り立つという定理です。数オリ予選の3～4問目ぐらいのGによく出るイメージ。また、Bが円の外側にある場合(図2)や$${BE}$$が円に接する場合(図3)も同様に成り立ちます。相似を利用することで証明できるので、やったことがない方はぜひやってみてください。
トレミーの定理 ★★★
上の図において、$${AB \times CD + AD \times BC = AC \times BD}$$が成り立ちます。これをトレミーの定理といいます。
・使う問題
OMCB015E
OMC084E
加法定理 ★★★
$$
sin(\alpha + \beta) = sin(\alpha)cos(\beta) + cos(\alpha)sin(\beta)
\\
cos(\alpha + \beta) = cos(\alpha)cos(\beta) - sin(\alpha)sin(\beta)
\\
tan(\alpha + \beta) = \frac{tan(\alpha) + tan(\beta)}{1 + tan(\alpha)tan(\beta)}
$$
という定理です。OMCの低難易度幾何で見る場面は少ない気がします。でも超重要なので覚えておきましょう。
正弦定理 ★★★
三角形$${ABC}$$に内接する円$${\Gamma}$$の半径を$${R}$$とすると、
$$
\frac{AB}{sin(\angle ACB)} = \frac{BC}{sin(\angle BAC)} = \frac{CA}{sin(\angle CBA)} = 2R
$$
が成り立つという定理です。
・使う問題
余弦定理 ★★★
三角形$${ABC}$$において、
$${AB^2 = BC^2+CA^2-2\times BC\times CA \times cos(\angle ACB)}$$
が成り立つという定理です。他の二辺でも同様に成り立ちます。
・使う問題
OMC070D
OMCB015E
OMCB019D
三角関数・その他 ★★★
・使う問題
OMC039C
チェバ、メネラウスの定理 ★★★
AD、BE、CFが一点Gで交わるときに、
$$
\frac{AF}{FB}\times \frac{BD}{DC} \times \frac{CE}{EA}=1
$$
が成り立つのがチェバの定理で、
$$
\frac{AG}{GD}\times \frac{DB}{BC} \times \frac{CE}{EA}=1
$$
が成り立つのがメネラウスの定理。
意外とこういうのが盲点になったりします。辺の比を簡単に求められるので便利。
・使う問題
OMC027C(難)
OMC031C
中線定理 ★★★
下図において、$${D}$$が$${BC}$$の中点である時、$${AB^2＋AC^2=2(AD^2＋BD^2)}$$が成り立つというものです。スチュワートの定理という拡張があるが、それは後述する(予定です)。
・使う問題
OMC033C
直交座標 ★★★
僕はG弱なので基本これを使っています()
ある程度制約が強く、垂線が多い問題で威力を発揮します。機械的に解けるのが強い。ただし、角度を求める問題や円が多い問題になると手も足も出なくなるので諦めましょう。
・使う問題
OMC023D(めっちゃ頑張ったらできたけど座標は非推奨)
OMC043C
OMC045B
OMC049E
OMC066D
OMCB019D
イギリス国旗の定理 ★★★
Wikipediaの記事などをご覧ください。使う場面が限られるので、出てきたらすぐにこれを使うとわかります。
・使う問題
OMC058E
スチュワートの定理 ★★★★
この記事などを参照。中線定理などの上位互換です。
・使う問題
OMC072D
N
素数 ★
1とその数自身以外に約数を持たない数のことをいいます。整数問題で、素数であることを意識すると解が絞れることがままあります。
・使う問題
OMC031B
OMC041B
OMC063B
平方数 ★
平方数とは、ある自然数Nを用いて$${N^2}$$と表される数のことです。頻出で、特筆に値する性質がたくさんありますが、とりあえず
・平方数の約数は奇数個ある
・平方数を3で割った余りは0か1(2にはならない)
・平方数を8で割った余りは0か1か4
の3つを覚えておくとよいでしょう。
・使う問題
OMC025A
OMC066B
OMCB019C
最大公約数 ★
数a,bが共通に含む最大の約数をa,bの最大公約数と呼びます。a,bの最大公約数が1の時、a,bは互いに素であるといいます。
・使う問題
OMC065D
最小公倍数 ★
数a,bの共通の倍数としてあり得る最小の数を最小公倍数と呼びます。
整数a,bの最小公倍数をLCM(a,b)、最大公約数をGCD(a,b)とした時に、
$${ab=LCM(a,b)GCD(a,b)}$$となるのは覚えておくとよいと思います。
また、「aとbの最小公倍数が72になるようなa,bはいくつあるか」といった問題は、72を素因数分解して$${2^33^2}$$と表した時に、
$$
\begin{array}{} max(aを素因数分解したときの2の指数,bを素因数分解したときの2の指数)=3, \\\ max(aを素因数分解したときの3の指数,bを素因数分解したときの3の指数)=2 \end{array}{}
$$
となる2、3以外に素因数を持たない数を探せばよいです。
・使う問題
OMC021B
OMC052C(C)
OMC065D
合同式 ★★
ある数$${p}$$で割った余りだけを考えて計算するという考えです。必須スキルです。高校数学の美しい物語の記事などで基本的な計算方法は身に着けておきましょう。
・使う問題
OMC055A
三角数 ★★
自然数nについて、1からnまでの自然数をすべて足し合わせた数を三角数といいます。三角数を求める公式は
$$
\frac{n(n+1)}{2}
$$
・使う問題
OMC023C
OMC033A(A)
OMC055D(C)
約数の個数の公式、約数の総和の公式 ★★
正整数Nが素数$${p_1, p_2\dots p_n}$$と正整数$${a_1,a_2\dots a_n}$$を用いて$${p_1^{a_1}p_2^{a_2}\dots p_n^{a_n}}$$と素因数分解される時、
約数の個数を求める公式は
$${(a_1 + 1)(a_2 + 1) \dots (a_n + 1)}$$
約数の総和を求める公式は
$${(1+p_1+p_1^2+\dots +p_1^{a_1}) (1+p_2+p_2^2+\dots +p_2^{a_2}) \dots (1+p_n+p_n^2+\dots +p_n^{a_n})}$$
です。
・使う問題
OMC075E
n進法 ★★
我々が普段使っている数は10を基準として表されます。例えば、1210は$${1\times 10^3+2\times 10^2+1\times 10^1+0\times 10^0}$$という意味です。この10を、任意の自然数nに置き換えたものをn進法と呼びます。
・使う問題
OMC033B(C)
OMC035A(C)
OMC055C
階乗 ★★
1からnまでの数をすべて掛け合わせたものをnの階乗と呼び、$${n!}$$と表します。合同式とかなり相性が良いです。階乗は急速に大きくなるので、たいていは後述するルジャンドルの定理などを用いて2などの指数を答えさせます。
・使う問題
OMC061C
OMC063B
不定方程式(一次＆二元) ★★
出る頻度は低いかもしれません。ユークリッドの互除法を用いる方法が有名ですが、前にXで見つけた方法にとても感動したのでここで共有しておきたいです。$${53x+31y=1}$$を例に説明します。
$$
\begin{pmatrix}53\\1\\0\end{pmatrix},\begin{pmatrix}31\\0\\1\end{pmatrix}
$$
を作り、後はユークリッドの互除法と同じように足し引きします。
$$
\begin{pmatrix}
53\\
1\\
0
\end{pmatrix}
-
\begin{pmatrix}
31\\
0\\
1
\end{pmatrix}
=
\begin{pmatrix}
22\\
1\\
-1
\end{pmatrix}
\\
\begin{pmatrix}
31\\
0\\
1
\end{pmatrix}
-
\begin{pmatrix}
22\\
1\\
-1
\end{pmatrix}
=
\begin{pmatrix}
9\\
-1\\
2
\end{pmatrix}
\\
\begin{pmatrix}
22\\
1\\
-1
\end{pmatrix}
-2\times
\begin{pmatrix}
9\\
-1\\
2
\end{pmatrix}
=
\begin{pmatrix}
4\\
3\\
-5
\end{pmatrix}
\\
\begin{pmatrix}
9\\
-1\\
2
\end{pmatrix}
-2\times
\begin{pmatrix}
4\\
3\\
-5
\end{pmatrix}
=
\begin{pmatrix}
1\\
-7\\
12
\end{pmatrix}
$$
ここで、真ん中が$${x}$$、下が$${y}$$の特殊解になっています。実際に、$${53\times (-7)+31\times 12=1}$$です。すごくないですか？
このことを載せるにあたり出典を探したのですが見つかりませんでした。何か知っていることがあれば教えてくださると幸いです。
・使う問題
OMC033D(A)
OMC072B
数列の和 ★★★
シグマ記号のやつですね。Cで見ることのほうが多い気がします。高校数学の美しい物語の記事がとても便利なのでぜひご覧ください。
・使う問題
OMC035B
OMC045D
OMC078D
OMC228B
ルジャンドルの定理 ★★★
$${n!}$$における$${n\geq p}$$を満たす整数$${p}$$の指数は
$$
\bigl \lfloor \frac{n}{p} \bigr\rfloor + \bigl\lfloor \frac{n}{p^2}\bigr \rfloor + \bigl\lfloor \frac{n}{p^3} \bigr\rfloor +\dots
$$
と表せるという定理です。OMCでは最終的な答えを求めるときによく使います。
・使う問題
OMC061C
OMC075D
popcount ★★★★
正整数$${N}$$ の二進法表示での $${1}$$ の数を $${popcount(N)}$$といいます。2の累乗がたくさん出てくるなあと思ったらpopcountを疑ってみてください。
・使う問題
OMC068E
中国剰余定理 ★★★★
この記事やこの記事を参照。合同式の方程式の解が一意に定まるという定理です。
・使う問題
OMC072F
$${v_2(x!)=x−popcount(x)}$$ ★★★★★
ただし、正整数 $${N}$$ が $${2}$$ で割り切れる最大の回数を $${v_2(N)}$$，$${N}$$ の二進法表示での $${1}$$ の数を $${popcount(N)}$$とします。
しましまさんのOMCの所属欄に書いてあるあれです。証明はbzuL様の解説から引用させていただきました。(一部改変しております)
$${x}$$ に関する帰納法によって示す．
まず，$${x=1}$$ のとき，両辺はともに $${0}$$ となり成立する．
次に，ある $${x≥1}$$ で成立していると仮定する．$${x}$$ を $${2}$$ 進表示したとき，$${2^0}$$ の位から $${k}$$ 個連続して $${1}$$ が現れるとする．このとき，
$${v_2(x+1)=k,popcount(x+1)=popcount(x)−k+1}$$
であるから，
$${v_2((x+1)!)=v_2(x!)+v_2(x+1)=(x+1)−(popcount(x)−k+1)=(x+1)−popcount(x+1)}$$
となる．以上より示された．
・使う問題
OMC039D