競技プログラミング用 知識集積所
ABC409C - Equilateral Triangle
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
まず、頂点の番号に意味はないので、どこにいくつ点があるかの情報に変換してしまって構わない。
さて、正三角形がどういう位置にできるか考えよう。
入力例1の場合、位置として{0,2,4}の位置関係か{1,3,5}の位置関係が正三角形ができる位置である。
つまり、円周を1/3ずつ進んだ位置関係になっている数値の組が何組あるかを数えればいい。
ということは、Lが3の倍数でない場合、そもそも不可能である。
入力例1の場合、位置として{0,2,4}の位置関係か{1,3,5}の位置関係が正三角形ができる位置である。
つまり、円周を1/3ずつ進んだ位置関係になっている数値の組が何組あるかを数えればいい。
ということは、Lが3の倍数でない場合、そもそも不可能である。
Lが3の倍数の場合、{0,2,4}の位置関係でできる正三角形の個数は、位置0にある点を1つ、位置2にある点を1つ、位置4にある点を1つ選べばいいので、順列組み合わせ（未作成）の積の法則を用いることができる。
最も小さい数がL/3より小さい全てのパターンについて正三角形の個数を求め、合計すればよい。
最も小さい数がL/3より小さい全てのパターンについて正三角形の個数を求め、合計すればよい。
解答例
注意点
long long型を使用する
Nが非常に大きく、点が正三角形の3つの頂点に集中した場合、その三角形ができる個数はint型範囲を超えてしまう。
