嘘~ 正在从服务器偷取页面 . . .

[ARC129C] Multiple of 7 题解

发布日期: 2023-05-16

更新日期: 2023-05-16

文章字数: 610

[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;
}