[ARC129C] Multiple of 7 题解

题意：

给定一个整数 N。

找到一个由数字 1 到 9 组成的字符串 s，满足以下条件：

s 的长度 \(\vert s \vert\) 最多为 \(10^6\)。

有恰好 N 对整数 \((l,r)\) \((1 \leq l \leq r \leq \vert s \vert)\) 满足以下条件。

当将 s 的第 l 到第 r 个字符提取出来看作一个数时，该数能被 \(7\) 整除。

在这个问题的约束条件下，我们可以证明一定存在一种解法。

数据范围：

\(1 \leq N \leq 10^6\)

这个 \(7\) 真的是非常独特啊，因为它是个位数中最大的质数。

同时样例2的 \(\tt{77}\) 也提示了我们，这道题可能需要构造若干 \(\tt{77777}\) 的子串，并拼接他们。

可以发现长度为 \(k\) 的 \(\mathtt{77777}\) 串的贡献为 \(\frac{k(k+1)}{2}\) ，在 \(10^6\) 的限制下实际串上 \(k\) 不会超过 \(2000\) 。

但是问题来了，用什么字符拼接这个 \(\tt{77777}\) 的子串呢？好像如何拼接都可能被卡。

这个时候就要利用 \(\tt{7}\) 的质数性质了。考虑用随机个位数作分隔符。

由于形如 \(\tt{777a77}\) 的数过于特殊，并且需要被质数 \(7\) 整除，所以实际的随机次数不会很多。

时间复杂度 \(\mathcal{O}(cn)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define q779_does_not_have_a_girlfriend true
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int n,cnt,sum[N],num[N]; string buf;
void init()
{
    for(int i = 1; i <= 2333; i++) sum[i] = i * (i + 1) / 2;
}
void solve(int x)
{
    for(int l,r; x; )
    {
        for(l = 1, r = 2222; l < r; )
        {
            int mid = (l + r + 1) >> 1;
            (sum[mid] <= x) ? (l = mid) : (r = mid - 1);
        }
        x -= sum[l]; num[++cnt] = l;
    }
}
string make(int x)
{
    string tmp = ""; while(x--) tmp += '7';
    return tmp;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; init(); solve(n); mt19937 rd(time(0));
    while(q779_does_not_have_a_girlfriend)
    {
        buf.clear(); for(int i = 1; i <= cnt; i++) {
            buf += make(num[i]);
            if(i != cnt) buf += char(rd() % 9 + '0');
        }
        int ok = 0;
        for(int i = 0, x = 0; i < buf.size(); i++, x = 0)
            for(int j = i; j < buf.size(); j++) {
                ok += (!(x = ((x * 10) + buf[j] - '0') % 7));
            }
        if(ok == n) return cout << buf << '\n', 0;
    }
    return 0;
}