2023-02-27 nostr-keygen 0.1.0 をつくった / ARC149 の A を解いた
nostr-keygen 0.1.0 をつくった。 bouzuya/rust-sandbox に置いている。
nostr-keygen は prefix を指定して nostr で使用するための keypair を生成するコマンド。 nostr では public key が露出していることも多いので「良い感じ」の keypair が欲しくなったのでつくった。
NIP-19 https://github.com/nostr-protocol/nips/blob/master/19.md に書かれているとおり nostr では bech32 形式で public key を表示することが推奨されている。この形式にしたとき「良い感じ」のものが欲しい。
nostr-keygen で 60 を prefix に指定すると、例えば npub160ulkrt40kpqtr6l3jd20tcswuykx2wkfwn6pskn8d8rp0c3dznsvd7tm4 が得られる。
bech32 形式では '1', 'b', 'i', 'o' をデータに使えない。 bouzuya は bo からはじまるので残念だけど 60 で探している。
60uzu からはじまる keypair は得たのだけど、どうせなら 60uzuya を目指してみている。文字種が 32 で 7 桁なので 32 ^ 7 = 34_359_738_368 。毎秒 5_000 個くらいは試せるけど、このペースだと 80 日くらいかかるのか……。やめたほうがよさそう。
ARC149 : AtCoder Regular Contest 149 の A を解いた。
- A - Repdigit Number
https://atcoder.jp/contests/arc149/tasks/arc149_a
- 提出: https://atcoder.jp/contests/arc149/submissions/39295894
1..=Xを確認するのは間に合わない- M の倍数を順に探すのも間に合わない
- 各桁の数字は
1..=9で、それぞれ最大 10^5 桁なので、すべて試しても間に合う - 愚直に剰余をとって M の倍数かを確かめるには数字が大きすぎる
- 下の桁から順に
((10 * x) % m + d) % mする - 結果が 0 (M の倍数) になる、桁と数字を記録する
- 最大の桁数のもの、桁数が同じなら数字の大きいものを選んで出力すれば答えになる
- 選べなかったときは
-1
use proconio::input;
fn main() {
input! {
n: usize,
m: usize,
};
let mut ans = (0, 0);
for d in 1..=9 {
let mut maxlen = 0;
let mut x = 0;
for len in 1..=n {
x = ((10 * x) % m + d) % m;
if x == 0 {
maxlen = maxlen.max(len);
}
}
if maxlen > 0 && maxlen >= ans.0 {
ans = (maxlen, d);
}
}
if ans == (0, 0) {
println!("-1");
} else {
for _ in 0..ans.0 {
print!("{}", ans.1);
}
println!();
}
}
今日のコミット。