Skip to content

Instantly share code, notes, and snippets.

@kirika-comp kirika-comp/BROCLK.md
Last active Feb 14, 2018

Embed
What would you like to do?

Broken Clock u=cos(a)が与えられるから、cos(ta)を求めよ、という問題です。

(部分点についてのあれこれ)

満点解法について説明します。ここで天下り的ですが、cos(a)とsin(a)=sqrt(1-u^2)を考えて、(cos(ta),sin(ta))をcos(a),sin(a)の式で表すことを考えます。

de Moivreの定理から、cos(ta)+i sin(ta) = (u + sqrt(1-u^2)i)^t です。ここで、ペア(x, y) が複素数x + sqrt(1-u^2)yi を表すと思うと、 これらについての掛け算が定義できます。このため、二分累乗法が使えます。

つまり、mul((x, y), (z, w)) = (x * z + (u^2 - 1) * y * w, x * w + y * z) とすると、これは結合法則を満たす演算で、累乗が定義できます。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.