naoya_t@hatenablog

いわゆるチラシノウラであります

拡張ユークリッド互除法の話

先日の連分数の計算と拡張ユークリッド互除法って少し似てるなと思ったというメモ。(連分数の計算で次の項を求める時にやっている操作ってユークリッドの互除法そのものだし当然か)

拡張ユークリッド互除法というのは、ax+by=gcd(a,b) を満たすx,y\in\mathbb{Z} を求める方法。
a,bgcd(a,b) で割れば a'x+b'y=1(a'とb'は互いに素)という形になる。

続きを読む

Crayfish Scrivener (IOI 2012, day 1)

6月は永続データ構造強化月間(そういうことにしました)、ということで
qnighy先生の
Re永続データ構造が分からない人のためのスライド
で紹介されていた、IOI 2012の"Crayfish Scrivener"を解いてみたメモ。

続きを読む

連分数 (continued fraction)

連分数 - Wipikedia

こないだのJune Long ChallengeのEuler Sumを考えてる時に
Mark Jason Dominus氏のスライド
Arithmetic with Continued Fractions
を読んだ時のメモ。

連分数とかいじるのって多分昔SICPを読んだ時以来。

続きを読む

小さい数n(100万までとか)の素因数分解

CodeChefのフォーラムで June Challenge 2017の問題 Chef and Prime Queries (PRMQ) の解法を読んでいて
discuss.codechef.com

素因数分解をするのに

This can be done by creating a Smallest Prime Factor array in the sieve function itself.

とあって。エラトステネスの篩 (Sieve of Eratosthenes) をするときに、篩と同時に一番小さい素因数のテーブルを作ってしまえば素因数分解が簡単、っていう話。

続きを読む

TopCoder Marathon Match 93

最近ではすっかり英会話仲間なagwたんに再三誘われてたのもあり
久しぶりにMarathon Matchに出てみた話。

Marathon Match 93 (3/1 23:00EST〜3/16 0:00EDT)


最後に出たMMは4年前のTCO13らしい。
(問題文だけはとりあえず読んだもののあまり気乗りがしなくて参加に至らず、というのは何度かあった気がする。)

今回のMMの目標は、とりあえずyellow coderに上がること。(現在のratingは1424)

↓黙って出てたけど捕捉されてる

続きを読む

GCCのビルトイン関数メモ

http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html より

関数名末尾に l が付いてるのは long、ll なら long long、無印は unsigned int。
他にもいろいろあるけど、コンテストで使うかもしれないやつだけとりあえず。

__builtin_popcount, __builtin_popcountl, __builtin_popcountll

立ってるビット数を数えて返す
0x11 (2進で10001) なら2
0x57 (2進で1010111) なら5

__builtin_parity, __builtin_parityl, __builtin_parityll

立ってるビット数の偶奇を返す。(popcount % 2 に相当)
0x11 (2進で10001) なら0(偶数)
0x57 (2進で1010111) なら1(奇数)

__builtin_ffs, __builtin_ffsl, __builtin_ffsll

2進で表した場合に小さい方から何桁目に初めて1が現れるか。
0x07 (2進で111) なら1。0x08 (2進で1000) なら 4。
0の場合は0を返す。

__builtin_clz, __builtin_clzl, __builtin_clzll

2進で表した場合に左側にいくつ0を埋める必要があるか (the number of leading 0-bits in x)
(32bit unsigned intの場合)0x07 (2進で111) なら29。
0の場合は未定義。

__builtin_ctz, __builtin_ctzl, __builtin_ctzll

2進で表した場合に、1の位からいくつ0が連なっているか (the number of trailing 0-bits in x)
0x08 (2進で1000) なら3。
0の場合は未定義。