一般に、正n角形の各頂点は円周上の θ = 2π * k/n (0≦k＜n) の点として表せます。 逆に単位円上の点を列挙しようと思ったら、上の式で n→∞ としてやればよさそうです。Haskell で書くとこんなかんじ。zeroToOne は区間[0,1)の全ての有理数を列挙する無限リス…

Problem 159 素直にやると Σ(約数の個数)/2 ぐらいの時間かかって、でも良いアルゴリズム思いつかないしなぁと放置してたんですが、Cで力まかせにいくかーと思って書いたら1秒くらいで終わって拍子抜けした。約数の個数って、でかくなりうるイメージが漠然と…

一般項が、Fibonacci数を求めるプログラムにどの程度使えるか検証してみる。 無理数絡みなので、どのあたりで誤差が出るのかが興味の対象。 #include <iostream> #include <cmath> using namespace std; const double R5 = sqrt(5.0); //typedef int num_t; typedef long long</cmath></iostream>…

totient function って何だろうと思ったら、Eulerのφ関数のことだった。Φ関数は公式をそのまま実装できるけど、m,n が互いに素のとき、Φ(mn) = Φ(m)Φ(n) という性質を利用して DP するのが速い。

また忘れ物。 http://yosshy.sansu.org/chofuku.htm ｎ種類のボールがそれぞれ無制限にたくさんあり、それらの中からｍ個を取り出す取り出し方。 ｍ人の人を、ｎ個の部屋（定員無制限）に割り振るやり方。部屋は区別するが、人は区別しない。 → m 個の○と (n…

fの不定和分が分かると、f(x) の総和を効率よく求めることができる。 http://acm.uva.es/p/v103/10302.html 降べき x^{n} を以下のように定義する x^{n} = x * (x-1) * ... * (x-n+1) 差分/和分では、x^{n} が微分/積分における x^n と似た挙動をする。 n * …

初等数学公式集 三角形の面積公式とか。要復習。

Goldbach's Conjecture In 1742, Christian Goldbach, a German amateur mathematician, sent a letter to Leonhard Euler in which he made the following conjecture: (A) Every number greater than 2 can be written as the sum of three prime numbers.…

問題 input: 整数 n output: k = 整数 n の約数の個数 とする。このとき k が奇数ならば yes, 偶数ならば no n の約数を並べてみると、 となる。ここでポイントになるのが次の命題 任意の について が成り立つ。 つまり、約数列の前から i 番目と後ろから i …