ARC 129 - C 多角数定理

https://atcoder.jp/contests/arc129/tasks/arc129_c

$ $
$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$なので、これは大丈夫。幾つか試す。

```math
\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の表現に手こずり終了した。

# 四平方定理

ここからあとはコンテスト終了後。
高々６つの組み合わせで良いことは分かったが、もっと少ない要素で何とかならないか。
こんな定理が見つかった。覚えておいた方が良い。

https://ja.wikipedia.org/wiki/四平方定理

「全ての自然数は高々四個の平方数の和で表される」

今回は平方数ではないが、「高々四個の$\frac{k(k+1)}{2}$の和で表される」のではないかという期待はできる。プログラムを組んで検証したところ少なくとも$N≤100000$の範囲では問題ないことがわかり、なんとかACにたどりつき、この記事を書こうとするに到った。そしてWikipediaで調べていて衝撃の事実。

# 多角数定理

https://ja.wikipedia.org/wiki/多角数定理

$ $「全ての自然数は高々$m$個の$m$角数の和で表される」
四平方定理は$\,m=4$の場合とのこと。

$m=3$の場合は「全ての自然数は高々三個の三角数の和で表される」であり、
そして三角数は$\frac{k(k+1)}{2}$のことらしい。
「４つ組み合わせてみる」以降の考察は不要だったわけである。

$f(X) + f(Y)+ f(Z) = N$をみたす数の組$(X,Y,Z)$を求めるのは[Otoshidama](https://atcoder.jp/contests/abs/tasks/abc085_c)と同じ。

以下解法。

$ $
・$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解法

https://atcoder.jp/contests/arc129/submissions/27493266

```rust:arc129_c.rs
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

全ての自然数は高々４つの平方数の和で表される。
全ての自然数は高々３つの三角数の和で表される。