Skip to content

Instantly share code, notes, and snippets.

@kirika-comp kirika-comp/
Last active Feb 14, 2018

What would you like to do?

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



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.