nekopon (1483) の日記
割られる数をnとおきます
- 最下位ビットを別途取っておきます(n0 = n & 1)
- nを1ビット右シフト(n >>= 1)
- 残りを4ビットごとに区切って和を取ります
- n = ((0xf0f0f0f0 & n) >> 4) + (0x0f0f0f0f & n)
- n = (n >> 16) + n
- n = (n >> 8) + n
- n &= 0xf
- 残りが0-15になるのですが5で割った剰余を求めます
- 表引きでもよし (tmpres = 0x0432104321043210 >> (n << 2))
- if (((n >> 2) & 3) > (n & 3)) {
tmpres = 5 + (n & 3) - ((n >> 2) & 3);
} else {
tmpres = (n & 3) - ((n >> 2) & 3);
}
- 上記でfloor(n/2)を5で割ったあまりが求まるので、10で割ったあまりにするには
2倍してn0を足します (return (tmpres << 1) | n0)
これ5が22+1であるというところに鍵があったりします。
- x ≡ 1 (mod yz) のとき x ≡ 1 (mod y)
- x ≡ 1 (mod (x-1))
- x ≡ 1 (mod y) ならば x2 ≡ 1 (mod y)
なので
22k ≡ 1 (mod (22k) - 1)
22k ≡ 1 (mod (2k + 1))、ゆえに
24 (=16) ≡ 1 (mod 22 + 1 (=5))、さらに
24 x 2 ≡ 1 (mod 5)
ということで4ビットごとに区切って足していけば剰余が求まるというわけです。
もひとつ
- x ≡ -1 (mod x+1)
すなわち4 ≡ -1 (mod 5)なのが最後の if 文の表現であります。
剰余が出るだけで商は出ないので無能
- 12 コメント
どうやってもマイナートラブルだから (駄洒落
- 1 コメント
夜間には達成されそうな予感(よろ
- 1 コメント
https://www.nikkei.com/article/DGXZQOUC151BN0V11C21A2000000/
- 4 コメント
https://xtech.nikkei.com/atcl/nxt/column/18/01651/070200013/
- 3 コメント
1兆円規模の契約をさくっと取り消しとはまた剛毅な
https://xtech.nikkei.com/atcl/nxt/news/18/10762/
- 0 コメント
- 0 コメント
スラド的には黄猿よりこっちかな
- 0 コメント