arc129 C – Multiple of 7

题意：

给定 \(n\)，请构造一个长度不超过 \(1e6\) 的 1~9 串 \(s\)，满足视为数字时被 \(7\) 整除的子串恰有 \(n\) 个

\(n\le 1e6\)

思路：

\(s[l..r]\) 能被 \(7\) 整除，即 \(7 | \frac{s[l..end]-s[r+1..end]}{10^?}\)

分母与 \(7\) 互质，所以只需 \(s[l..end]\equiv s[r+1..end]\pmod 7\)

设 \(a_i:=s[i..end]\mod 7\)，设 \(c[]\) 为数组 \(a[]\) 的桶，即 \(c_v=\sum\limits_i [a_i=v]\)

那么我们要构造数组 \(c[]\)，使得 \(n=\sum\limits_i c_i(c_i-1)/2\)

问题是怎么构造？如果你经验丰富（呃呃），或者你打个表（呃呃），就能发现在这题的范围内，只需贪心地每次找满足 \(c_i(c_i-1)/2\) 的最大的 \(c_i\)

ps. 事实上 \(x(x-1)/2\) 恰好是三角形数，\(c[]\) 的存在性由费马多边形数定理（Fermat polygonal number theorem）保证。详见 多边形数、费马多边形数定理、四平方和定理与华林问题

ps. 有了 \(c[]\) 后，从右到左构造答案字符串，每一位从 \(1\sim 7\) 试填即可

void sol() {
    int n; cin >> n;
    vector<int> c;
    while(n) {
        int x = 2; while(x * (x + 1) / 2 <= n) x++;
        c.push_back(x);
        n -= x * (x - 1) / 2;
    }
    c[0]--; // s[|s|+1]本就是0,不用搞
    vector<int> ans;
    int r = 0, w = 1;
    for(int i = 0; i < c.size(); i++) while(c[i]--) {
        int x = 1; while((r + x * w) % 7 != i) x++;
        assert(x < 8);
        ans.push_back(x);
        r = (r + x * w) % 7, w = w * 10 % 7;
    }
    for(auto i = ans.rbegin(); i != ans.rend(); i++)
        cout << *i;
}