Search on the blog

2011年12月27日火曜日

平方数について

平方数について簡単なまとめ。

1.平方数とは?
整数の二乗で表すことのできる数のこと。0, 1, 4, 9, 16, ...と続く。

2. 2つの平方数の和
2つの平方数の和に関しては、フェルマーのクリスマス定理が有名。この定理では奇素数が2つの平方数の和で表すことができるか否かについて述べられているが、

(x12 + y12)(x22 + y22) = (x1x2 - y1y2)2 + (x1y2 + y1x2)2

の公式より、一般の自然数nについて以下のことが言える。

n = n12 * n2, ただし、n2は法4の下で3と合同な奇素数を因数にもたない。

と分解できる場合、nは2つの平方数の和で表すことができる。上記のように分解できない場合は2つの平方和で表すことはできない。

3. 3つの平方数の和
3つの平方和ですべての自然数を表すことができるか?答えはできない。法8の下で7と合同な自然数は3つの平方数の和で表すことはできない。なぜなら、平方数は8を法として{0, 1, 4}のいずれかと合同になるが、これらの任意の3つの組み合わせの和は7と合同になりえないからである。

4. 4つの平方数の和
4つの平方数の和を用いれば、2. および3.で表すことができなかった自然数を表すことができる。
7 ≡ 3 (mod 4)および7 ≡ 7 (mod 8)より、7は2つの平方数の和でも3つの平方数の和でも表すことができない。しかし、

7 = 1+1+1+4

と4つの平方数の和で表すことができる。

すべての自然数は、4つ以下の平方数の和で表すことができる。定理の名前は知らなかったが、「ラグランジュの四平方定理」というらしい。

2011年12月20日火曜日

SRM 527 DIV1 450 P8XMatrixRecovery

2部グラフのマッチングまでは、気付いてた。あと一歩だった。
"ある条件を満たす辞書順最小のものを求めよ。"という問題はgreedyで解ける場合が多いような気がする。
int r;
int c;
bool edge[60][60];
bool used[60];
int pr[60];

class P8XMatrixRecovery {
bool dfs(int s) {
used[s] = 1;

REP(v, 2*c) {
if (!edge[s][v])
continue;
int w = pr[v];
if (w == -1 || (!used[w] && dfs(w))) {
pr[s] = v;
pr[v] = s;
return true;
}
}
return false;
}

int match(vector<string> &rows, vector<string> &cols) {
memset(edge, 0, sizeof(edge));
REP(i, c) REP(j, c) {
edge[i][j+c] = edge[j+c][i] = 1;
REP(k, r) {
if (cols[j][k] != '?' && rows[k][i] != '?' && rows[k][i] != cols[j][k]) {
edge[i][j+c] = edge[j+c][i] = 0;
break;
}
}
}

int ret = 0;
memset(pr, -1, sizeof(pr));
REP(i, 2*c) {
if (pr[i] >= 0)
continue;
memset(used, 0, sizeof(used));
if (dfs(i))
++ret;
}

return ret;
}

public:
vector<string> solve(vector<string> rows, vector<string> columns) {
r = rows.size();
c = rows[0].length();

REP(i, r) REP(j, c) {
if (rows[i][j] == '?') {
rows[i][j] = '0';

if (match(rows, columns) < c)
rows[i][j] = '1';
}
}

return rows;
}
};

2011年12月15日木曜日

メルセンヌ素数と完全数の関係

メルセンヌ素数と完全数には面白い関係がある。

1. メルセンヌ素数とは?
 メルセンヌ素数とは、メルセンヌ数かつ素数であるような数のこと。メルセンヌ数とは、2k-1という形で表される数のことで、2進数で表したときに、1のみで構成される数のことである。

2. 完全数とは?
完全数とは、その数のproper divisor(自分以外の約数)の和が自分自身と等しいような数のこと。
6 = 1 + 2+ 3
28 = 1 + 2 + 4 + 7 + 14
が最初の2つの完全数である。

3. 面白い関係って?
 メルセンヌ素数と完全数の間には以下の定理が成り立つ。
メルセンヌ数2k-1が素数であるとき、2k-1(2k-1)は完全数である。逆に、すべての偶数の完全数は、2k-1(2k-1)という形(2の冪乗とメルセンヌ素数の積)で表現できる。(※注意

 証明のために関数σを導入します。σ(n)は、nの約数(properな約数ではなく、自分自身も含むことに注意)の和を表します。例えば、
σ(6) = 1 + 2 + 3 + 6 = 12
です。nが完全数の場合は、σ(n) = 2nです。
 
 この関数σについて以下の補題を考えます。
N = ab(a, bは互いに素)と表せるとき、σ(N) = σ(a) * σ(b)である。

 証明) σ(a) * σ(b) = (a1 + a2 + a3 + ... ) * (b1 + b2 + b3 + ... ) = Σ(aの約数 * bの約数)である。ここでa1,a2,..はaの約数、b1,b2,..はbの約数である。よって、(aの約数 * bの約数)がNの約数となることと、Nの任意の約数dがある一組の(i, j)についてd = ai * bjとなることを示せばよい。
 まず前半だが、a, bが互いに素であるため、a x + b y = 1となるような整数(x, y)が存在する。両辺にNをかけると、a x N + b y N = Nとなる。aの約数 | a かつ bの約数 | Nなので、(aの約数 * bの約数)はa x Nを割りきる。同様に(aの約数 * bの約数)はb y Nを割りきる。よって(aの約数 * bの約数)はNを割りきる。
 次に後半を示す。a, bの素因数分解を
a = p1k1p2k2p3k3...pnkn
b = q1t1q2t2q3t3...qmtm
と表記する。ki > 0, i = 1,2,...n、およびtj > 0, j = 1,2,..mである。また、aとbが互いに素なので、pi≒qj, i=1,2,..n, j =1,2,...mである。
N= a * bなので、Nの素因数分解は
N = p1k1p2k2p3k3...pnkn q1t1q2t2q3t3...qmtm
となる。ここで、Nの任意の約数は、
x = p1k'1p2k'2p3k'3...pnk'n q1t'1q2t'2q3t'3...qmt'm
と表すことができる。ただし、0 ≦k'i ≦ki, i = 1,2,...n、0 ≦ t'j ≦tj, j=1,2,...,m.である。
Nの任意の約数を選ぶことと、(k'1,k'2, ..., k'n, t'1,t'2,..., t'm)の値を決めることは一対一に対応している。(k'1,k'2, ..., k'n, t'1,t'2,..., t'm)が決まれば、(k'1,k'2, ..., k'n)、(t'1,t'2,..., t'm)が決まり、これは、対応するaの約数、bの約数が一意に決まることを意味する。□

 それでは、メルセンヌ素数と完全数に関する定理の証明に入ります。まず、最初の部分を証明します。
2k-1は素数なので、σ(2k-1) = 1 + 2k-1 = 2kです。2k-1は、2のべき乗なので約数は1, 2, 22, .... 2k-2, 2k-1である。よって、σ(2k-1) = 1 + 2 + 22 + ... + 2k-1 = 2k-1。2k-1(2の冪乗)と2k-1(奇数)は互いに素なので補題より、σ(2k-1(2k-1)) = σ(2k-1) * σ(2k-1) = (2k-1) * 2k = 2 * 2k-1(2k-1)となる。
σ(n) = 2nなので、2k-1(2k-1)は完全数である。

 次に後半を示す。偶数の完全数を2k-1mと表記する。ただし、k≧2、mは奇数。
補題よりσ(2k-1m) = σ(2k-1) * σ(m) = (2k-1) σ(m)。
また、2k-1mは完全数であることから、σ(2k-1m) = 2 * 2k-1m = 2km。
よって、
2km = (2k-1) σ(m)。
ここで、(2k-1) | 2km、かつ2kと(2k-1)は互いに素であることから、(2k-1) | m。
よって、m = (2k-1) Mとして先ほどの式に代入すると
2k (2k-1) M = (2k-1) σ(m)となり、両辺を (2k-1) で割ると、
2kM = σ(m)。
m + M = (2k-1) M + M = 2kMより、σ(m) = m + Mとなるが、これはmが素数で、M=1であることを意味する。よって、m = 2k-1(素数)となり、もともとの完全数は、2k-1(2k-1)と表される。□

(※注意)奇数の完全数が存在するか否かは不明です。現時点で発見されている完全数はすべて偶数です。

参考:

2011年12月12日月曜日

n進数表記の数を(n-1)で割れるかどうか

面白い問題があったので、紹介。

 n進数表記の数値を(n-1)で割り切れるかどうかは、すべての桁の数値を足した数が(n-1)で割れるかどうかを調べればいいです。例えば、10進数表記の111111111、45、1233、123453は桁の合計値が9で割れるので9の倍数です。

 n進数表記のm桁の数 A = A_(m-1).. A_2 A_1 A_0について考えます。つまり、
A = A_(m-1) * n^(m-1) + ... A_2 * n^(2) + A_1 * n^(1) + A_0
です。 n = 1 (mod (n-1))なので、
A = A_(m-1) + ... + A_2 + A_1 + A_0 (mod (n-1))
です。
ということで、Aの各桁の合計値を出してそれが(n-1)で割れるかどうかをみればOKです。

 C++のスパゲッティなソースを張っておきます。(dividable()の中で毎回合計値計算してるのは無駄ですね。。最初まじめにHormerの公式を使って余りを計算して解こうとしていたのの名残です。)

int num[128];

bool dividable(int k, const string &str) {
    int len = str.length();
    int digsum = 0;
    REP(i, len) digsum += num[(int)str[i]];

    return digsum % (k-1) == 0;
}

int main() {
    string str;

    for (int i = '0'; i <= '9'; i++) num[i] = i - '0';
    for (int i = 'A'; i <= 'Z'; i++) num[i] = i - 'A' + 10;
    for (int i = 'a'; i <= 'z'; i++) num[i] = i - 'a' + 36;

    while (cin >> str) {
        int len = str.length();
        int base = 0;
        REP(i, len) base = max(base, num[(int)str[i]]);
        base = max(2, base+1);

        int k;
        for (k = base; k <= 62; k++)
            if (dividable(k, str))
                break;

        if (k <= 62) cout << k << endl;
        else cout << "such number is impossible!" << endl;
    }

    return 0;
}

2011年12月8日木曜日

最大クリーク問題

http://poj.org/problem?id=3692
を解いていて、「最大クリーク問題」という問題について知った。

 与えられたグラフの部分グラフのうち完全グラフとなるものをクリーク(clique)と呼ぶ。節点数が最大となるクリークを求める問題を「最大クリーク問題」という。この問題はNP完全らしい。

 完全グラフの補グラフは、null graph(枝集合が空集合であるグラフ)であるので、あるグラフの最大クリークを求めることと、その補グラフの最大独立集合を求めることは同値である。

 二部グラフにおいては最小点カバーと最大マッチングが一致すること、および、一般のグラフにおいて最小点カバーと最大独立集合の和が節点数と一致することから、対象の補グラフが二部グラフである場合には最大クリークを簡単に求めることができる。

 ”クリーク”という言葉は、社会学から生まれたらしい。ソーシャルグラフの中からお互いが全員知り合いであるような最大集合の大きさを求めたいというのが研究のはじまり。まさに、PKUの問題もこれと同様の問題。実際のソーシャルグラフの補グラフは必ずしも二部グラフになるとは限らないため、さまざまな近似アルゴリズムが研究されているらしい。

 PKUの問題の解答例を載せておきます。

int n;
bool edge[400][400];
bool used[400];
int pr[400];

bool match(int s) {
    used[s] = true;
    REP(i, n) {
        if (!edge[s][i]) continue;
        if (pr[i] == -1 || (!used[pr[i]] && match(pr[i]))) {
            pr[s] = i;
            pr[i] = s;
            return true;
        }
    }

    return false;
}

int main() {
    int b, g, m;

    int t = 0;
    while (cin >> b >> g >> m) {
        if (!b && !g && !m) break;

        int x, y;
        n = b + g;
        REP(i, n) REP(j, n) edge[i][j] = 1;
        REP(i, b) REP(j, b) edge[i][j] = 0;
        REP(i, g) REP(j, g) edge[i+b][j+b] = 0;

        REP(i, m) {
            cin >> x >> y;
            --x, --y;
            edge[x][y+b] = edge[y+b][x] = 0;
        }

        int ret = n;
        memset(pr, -1, sizeof(pr));
        REP(i, n) {
            if (pr[i] == -1) {
                memset(used, 0, sizeof(used));
                if (match(i)) --ret;
            }
        }

        printf("Case %d: %d\n", ++t, ret);
    }

    return 0;
}


参考:
1. simezi_tanの日記
2. Clique problem - wikipedia

2011年12月4日日曜日

サーバー奮闘記(18) gitを使う


 結構前にgitはローカルとvpsともに入れていたのですが、GitHubにソースを上げるときくらいしか使ってませんでした。

 vpsにマスターのレポジトリを作って、ローカルにいくつかレポジトリを作ってpushしたりpullしたりして遊んでみました。簡単なメモを残します。

1. sshのconfigファイルの設定
 sshを使ってリモートログインしたいサーバーが複数台ある場合は、configファイルを書いておくと便利です。サーバーのアドレスや、sshのポート番号、どのrsa秘密鍵を使うのか、などを記述しておくと、sshコマンドを使う際にいろいろとオプションを書かなくてよくて楽です。

~/.ssh/config

HOST vps
 HostName 123.12.1.123
 Port 4321
 IdentityFile ~/.ssh/id_rsa_vps
 User taro

 それぞれのサーバーに付き、上のような設定を書いておくと、
ssh vps
のようにHOST名を書くだけでログインできるようになります。

2. サーバー側にbareリポジトリを作る
 調べてみた感じだと、2つやり方があるようです。1つ目は、サーバー上で普通のレポジトリを作成して、それをbareリポジトリにcloneして、さらにそれをローカルにcloneするという方法。2つ目は、サーバー側にbareレポジトリを作成して、クライアント側でリモートサーバーを登録する方法です。

1つ目の方法だと、cloneした時点で、push/pull先が自動でremoteに登録されるので明示的にリモートサーバー名を追加する必要はありません。ただし、サーバー側でcloneする前に、適当なファイルを作ってcommitしておかないといけません。

2つ目の方法は、サーバー側では
$ git --bare init
とするだけです。ただし、1つ目の方法と違って、remoteサーバー名が自動で登録されないので、サーバーに名前を付けたい場合(※)は、
$ git remote add origin ssh://vps/~taro/git/repos/hello
のようにremote サーバーを明示的に追加する必要があります。

※remoteサーバー名は必ず登録する必要はないですが、毎回push/pullする際に
$ git push ssh://vps/~taro/git/repos/hello
とするのは面倒なので、登録しておいた方が便利。

おそらく2つ目のやり方の方が一般的かと思います。

2011年12月1日木曜日

SRM 525 DIV2 950 MagicalSquare

DPで解く問題。どのような状態を保持するかが悩ましかった。最初、dp[r][i][j][k]としてr行目まで見たときに、各カラムが先頭からi, j, k文字まで埋まっている場合のパターン数を保持するようにした。しかしよく考えると、kはi, jが決まれば一意にきまるので、dp[r][i][j]とした。

 計算量は、(行数 4) * (カラムの埋まっている文字 50^2) * (現在注目している行の文字の分割パターン 50^2) * (文字列比較 50)であやしかったけど、投げてみる。TLE。ループの中にbreakを入れて枝狩りをしてみる。Accept。

 んー、通ったものの、計算量はもう一段階落ちると思う。文字列の比較をハッシュとか使ってやればいいのかなー。Editorialに期待します。


long long int dp[4][51][51];

class MagicalSquare {
public:
    long long int getCount(vector<string> rowStrings, vector<string> columnStrings) {
        memset(dp, 0, sizeof(dp));

        vector<string> rows(4);
        rows[0] = "";
        REP(i, rowStrings.size()) rows[i+1] = rowStrings[i];

        dp[0][0][0] = 1;
        int rLen[4];
        int cLen[3];

        REP(i, 4) rLen[i] = rows[i].length();
        REP(i, 3) cLen[i] = columnStrings[i].length();

        if (rLen[1] + rLen[2] + rLen[3] != cLen[0] + cLen[1] + cLen[2])
            return 0;

        int s = 0;
        REP (r, 3) {
            s += rLen[r];
            REP (i, cLen[0]+1) REP(j, cLen[1]+1) {
                if (!dp[r][i][j]) continue;

                int k = s - i - j;

                REP(p, rLen[r+1]+1) {
                    string s1 = rows[r+1].substr(0, p);
                    if (columnStrings[0].substr(i, s1.length()) != s1) break;

                    FOR (q, p, rLen[r+1]+1) {
                        string s2 = rows[r+1].substr(p, q-p);
                        string s3 = rows[r+1].substr(q);

                        if (columnStrings[1].substr(j, s2.length()) != s2) break;
                        if (columnStrings[2].substr(k, s3.length()) != s3) continue;

                        dp[r+1][i+s1.length()][j+s2.length()] += dp[r][i][j];
                    }
                }
            }
        }

        return dp[3][cLen[0]][cLen[1]];
    }
};