$ $
$1\dots9$の数字からなる文字列$,s,$がある。"17238971895475196"みたいな。
ここから連続した部分文字列("1723"、"7"、"5475196"など)を取り出して十進数として見る。
$7$の倍数となるものが幾つかある。$7$の倍数となる連続した部分文字列の個数取り出し方が$N$になるように$,s,$を作りなさいと。$1≤N≤10^6,;|,s,|≤10^6$。
つくってみる
$ $難しいので $|,s,|$が少ないものでつくってみる。
"7" → {"7"} $N=1$。
"77" → {"7", "7", "77"}
それぞれ$(l,r) = (1,1), (2,2),(1,2)$に相当。 $N=3$。
"777" → {"7", "77", "777",...}
$(l,r) = (1,1), (1,2),(1,3),(2,2),(2,3),(3,3)$ $N=6$。
$k$個の"7"のみからなる文字列"777...7"であれば、$\{(l,r);|;1≤l≤r≤|,s,|,\}$のすべてが$7$の倍数になる。
組み合わせの数は、$l<r$のとき$_kC_2$、$l=r$のとき$k$なのであわせて
$\frac{k(k-1)}{2}+k=\frac{k(k+1)}{2}$
$ $あたえられた$N$に対してちょうど$\frac{k(k+1)}{2}=N$となる$k$があれば、"77...7"("7"を$k$個並べたもの)が答えになる。
組み合わせてみる
$\frac{k(k+1)}{2}=N$となる$k$がない場合にどうするか。
たとえば$\frac{k_1(k_1+1)}{2}+\frac{k_2(k_2+1)}{2}=N$のように、２つの$k$を組み合わせることができれば、表現できる$N$の幅が広がる。
たとえば"777" → 3×4/2 = 6 通り、"7777" → 4×5/2 = 10 通りなのでこれを組み合わせて16通りになる文字列をつくりたい。"7777777"というふうに一つながりなってしまうと 7*8/2 = 28 で16にならない。間に1を挟んで"77717777"としてみる。
こうすると、"7177"など1をまたぐ文字列は7の倍数にならない。なぜなら$7177 = 7077 + 0100$で、$7077$は7の倍数だが$0100$は７の倍数でないから。
7の倍数となる組み合わせの数は、6+10 = 16通りとなる。
$ $あたえられた$N$に対し、ちょうど$\frac{k_1(k_1+1)}{2}+\frac{k_2(k_2+1)}{2}=N$となる$k_1$と$k_2$があれば、"77.7177..7"("7"を$k_1$個、"1"を1個、"7"を$k_2$個並べたもの)が答えになる。
３つ組み合わせてみる
$\frac{k(k+1)}{2}$をもっとくみあわせてみる。
"7177717777" → 1+6+10 = 17通り？
717など1を１つまたぐ場合は7の倍数にはならないが、"71777177"など２つまたぐ場合はどうか。
$71777177=70777077+01000100$で、$01000100=142871×7+3$なので、これは大丈夫。幾つか試す。
\begin{align}
11 &= 7 × 1 + 4\\
101 &= 7 × 14 + 3\\
1001 &= 7 × 143\\
10001 &= 7 × 1428 + 5\\
100001 &= 7 × 14285 + 6\\
\end{align}
1001は7の倍数。なので、
$71771777=70770777+01001000=70770777+1001×1000$
は7の倍数。1を2つまたぐ場合が7の倍数になるので、これは使えない。
少し変えて"717727777"にすると、1をまたぐ場合、2をまたぐ場合、1と2の両方をまたぐ場合いずれも7の倍数にはならないので、"7"と"77"と"7777"の場合の和に還元できる。
毎回1と2でいけるとは限らないが、$N$が3つの$\frac{k(k+1)}{2}$の組み合わせに分解できる場合はできそう。
４つ組み合わせてみる
$ $"77177177177"だと4つの77の組み合わせ。このままだと1001が絡んでくるので使えないが、適当な数字a, b, cを選んで"77a77b77c77"とすることで4つの$\frac{k(k+1)}{2}$の組み合わせに還元できるか。
この場合だと、$a00b00c$、$a00b$、$b00c$の全てを7の倍数でない状態にすることができればよい。$a$と$b$の候補は1から6の6通り。$c$を定めると$b00c$が7の倍数となる$b$は1通り。$b$と$c$を定めると$a00b$が7の倍数となる$a$は1通り、$a00b00c$が7の倍数となる$a$も1通りで2つの数字は使えないが、4つ余っており大丈夫。
$ $たとえば$b00c$の$c$を$1$とすれば、$b$は$1$以外ならよいので$2$とする。これで$a00b00c$は$a002001$となるが、$a002$は$a$が$2$以外ならよい。$a002001$は$a$が1以外ならよいので、$a$は$1,2$以外なら何でもよい。
4つの$\frac{k(k+1)}{2}$の組み合わせに分解することも可能だと分かった。
高々いくつまでの分解でよいか
$ $いくつの$\frac{k(k+1)}{2}$にまでなら分けてもよいか。"77a77b77c77d77e77f77g77"とかだと最後の方は選べる候補がなさそう。
$k$がなるべく大きくなるように貪欲的にとっていくと、たとえば$N=100000$のとき
$100000 = \frac{446 \centerdot 447}{2} + \frac{24 \centerdot 25}{2} + \frac{5 \centerdot 6}{2} + \frac{2 \centerdot 3}{2} + \frac{1 \centerdot 2}{2}$
少し調べると、少なくとも$N≤100000$であれば高々6つの組み合わせで済むことがわかった。
解法が見つかった。
$N= \Sigma_{i=1}^6\frac{k_i(k_i+1)}{2}$となるように$k_i$を定める。6より少なくてもよい。
"7a77b777c7777d7777e77777"のようなテンプレートに対し、a00bやb000c0000dなどが全て7の倍数でないようにa...eを定める
本番では、不定長で重複ありのpermutationの表現に手こずり終了した。
四平方定理
ここからあとはコンテスト終了後。
高々６つの組み合わせで良いことは分かったが、もっと少ない要素で何とかならないか。
こんな定理が見つかった。覚えておいた方が良い。
「全ての自然数は高々四個の平方数の和で表される」
今回は平方数ではないが、「高々四個の$\frac{k(k+1)}{2}$の和で表される」のではないかという期待はできる。プログラムを組んで検証したところ少なくとも$N≤100000$の範囲では問題ないことがわかり、なんとかACにたどりつき、この記事を書こうとするに到った。そしてWikipediaで調べていて衝撃の事実。
多角数定理
$ $「全ての自然数は高々$m$個の$m$角数の和で表される」
四平方定理は$,m=4$の場合とのこと。
$m=3$の場合は「全ての自然数は高々三個の三角数の和で表される」であり、
そして三角数は$\frac{k(k+1)}{2}$のことらしい。
「４つ組み合わせてみる」以降の考察は不要だったわけである。
$f(X) + f(Y)+ f(Z) = N$をみたす数の組$(X,Y,Z)$を求めるのはOtoshidamaと同じ。
以下解法。
$ $
・$N= \frac{x(x+1)}{2}+\frac{y(y+1)}{2}+\frac{z(z+1)}{2}$となるように$x,y,z$を定める。$0$でもよい。
・a0..(y個)..0bが7の倍数にならない$a,b$の組を1つ見つける。$a$は$1$に固定してよい。
・"7..(x個)..7a7..(y個)..7b7..(z個)..7"が答え
AC解法
use num_integer::Roots;
use proconio::input;
fn main() {
// 入力
input!{
n: usize,
}
// Nを３つの三角数に分解して生成元を返す
let gens = divide_to_tris(n);
// a00..0bが7の倍数にならないようなa, bを求める
let nums = find_num(gens);
let (x,y,z) = gens;
let (a,b) = nums;
// 7..(x個)..7a7..(y個)..7b7..(z個)..7 が答え
println!("{}{}{}{}{}", "7".repeat(x), a, "7".repeat(y), b, "7".repeat(z));
}
// nを3つの三角数に分解して生成元を返す O(n)
fn divide_to_tris(n: usize) -> (usize,usize,usize) {
// triは三角数を計算する関数(何もキャプチャしないクロージャ)
let tri = |x| x*(x+1)/2;
// rev_triはtriの逆関数だが小数部分は切り捨て
let rev_tri = |x: usize| ((1+8*x).sqrt() - 1) / 2;
for x in 0..=rev_tri(n) {
for y in x..=rev_tri(n-tri(x)) {
let z = rev_tri(n-tri(x)-tri(y));
if tri(x)+tri(y)+tri(z) == n {
return (x,y,z);
}
}
}
unreachable!();
}
// a0..(y個)..0bが7の倍数にならないようなa, bを求める O(y) < O(n^(1/2))
fn find_num((_x, y, _z): (usize, usize, usize)) -> (usize, usize) {
let a = 1;
let mut tmp = a;
// a0..(y+1個)..0を7で割った余りを求める
for _ in 0..y+1 {
tmp = tmp*10%7;
}
// a0..(y個)..0bが7で割り切れないようなbを求める
for b in 1..=6 {
if (tmp + b) % 7 == 0 { continue; }
return (a, b);
}
unreachable!();
}
Take Home Message
全ての自然数は高々４つの平方数の和で表される。
全ての自然数は高々３つの三角数の和で表される。