全通り試しても知れている。試す際はループ回数が少なくなるよう、$z$ からはじめ、1000000007ずつ加算して17と107の余りを確認する。
一応、2数なら機械的に求める方法がある。17と107に絞って考えると、
答えをnとおく 107k + y = n 5k + y = n mod 17 mod17で5の逆数を探すと、7 k + 7y = 7n mod 17 x = n mod 17 k + 7y = 7n = 7x mod17 k = 7(x-y) mod17
これによりkを求め、nを求める。
500円以上の部分は500円硬貨で支払うことになる。
1円,10円,100円は0～4枚、5円,50円は0～1枚しか使えないので、500円以外の硬貨は使っても14枚まで。
0～14枚の場合のパターン数を求めておくと、$0～min(14,N)$ のパターン数の合計が答え。
等角 $m$ 角形は、正 $m$ 角形からどれかの辺を平行移動を繰り返して作れる。 だが、平行移動した先にも $N$ 角形の頂点がちゃんとあるか、と考えると難しい。
ここは視点を変えて、「結んだ頂点はいくつ先か」に着目する。
頂点に時計回りに数字を振った時、1と3を結ぶと「2点先」である。
正 $N$ 角形からいくつかの頂点を結んで $m$ 角形を作る時、頂点の角度は両側の頂点がそれぞれ「何点先」かに依存する。
例えばある頂点について、左側の頂点が $a$ 点先、右側の頂点が $b$ 点先で、為す角が $\theta$ だとする。
その時、左側の頂点を中心に考えると、右側の頂点（つまり↑の頂点）が $a$ 点先、角度が $\theta$ であることは確定で、左側の頂点を決めなければいけない。これは、$b$ 点先しかない。
これを連鎖的に考えると、「順に何点先を拾っていくか」の列は $[a,b,a,b,...,a,b]$ か、$[c,c,...,c]$ の2パターンしかない。
この列はいずれも合計が $N$ となるように決める。
よって、$N$ の約数を列挙すると、
正1角形、正2角形は無いことに注意しつつ、以上を数え上げればよい。
誤差の問題と見せかけて（もちろんそれもあるが）オーバーフローの問題。
座標を求めるの自体は先頭から順番にやればよいが、$10^6$ 回も繰り返すと累積誤差は倍精度でも簡単に1の位にまで及んでくる。
よって、分子と分母を別々に持って分数として正確な演算を行うテクニックがまず考えられる。
Pythonでは、自分で実装せずともずばりfractions.Fraction型が使える。
しかし、例えば以下のような点の配置では、
A(-1000,1000) | B(1000,999)
|
---------------+----------------
|
C(-1000,-1000) | D(1000,-1000)
交点が(約400万,-1000)となり、更に同じようにすると交点のx座標を毎回約2000倍することが可能である。オーバーフロー不可避。
ここで終了条件を考えると、2線が交点を持つかどうかはABとCDの外積が0かどうかを判定すればよい。
大小比較はできないなど制限はあるが、一致判定のみなら、MODを有理数に拡張した概念を使えるらしい。へぇ。割り算は逆数をかける。
ただ、実際の座標を縮約しているので、上手い具合にハマってしまうと誤判定が生じる。生じる条件は理解できていない。