首先 \(\text{7777...777}\)（\(x\) 个 \(7\)）对能被 \(7\) 整除子串数量的贡献是 \(\frac{x(x+1)}{2}\)。
把 \(n\) 分解成若干 \(x_i\) 使得 \(\sum\limits_{i=1}^m \frac{x_i(x_i+1)}{2} = n\)，表示每段 \(x_i\) 个 \(7\)。怎么把它们组合在一起呢？
一个 naive 的想法是 \(\text{77...77a77...77a}\)，其中 \(a\) 为指定的数。发现怎么指定，中间都会串出一段 \(7\) 的倍数。
既然不能指定，那么就随机好了！随机得出每段 \(7\) 之间间隔的数，直到合法就输出，可过。
code
// Problem: C - Multiple of 7
// Contest: AtCoder - AtCoder Regular Contest 129
// URL: https://atcoder.jp/contests/arc129/tasks/arc129_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 1000100;
int n, m;
char s[maxn];
void solve() {
scanf("%d", &n);
int t = n;
vector<int> vc;
while (n) {
int l = 1, r = 1e4, pos = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (mid * (mid + 1) / 2 <= n) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
vc.pb(pos);
n -= pos * (pos + 1) / 2;
}
mt19937 rnd(time(NULL));
while (1) {
m = 0;
for (int x : vc) {
for (int _ = 0; _ < x; ++_) {
s[++m] = '7';
}
s[++m] = '1' + rnd() % 9;
}
int cnt = 0;
for (int i = 1; i <= m; ++i) {
int x = 0;
for (int j = i; j <= m; ++j) {
x = (x * 10 + s[j] - '0') % 7;
cnt += (!x);
}
}
if (cnt == t) {
break;
}
}
printf("%s\n", s + 1);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}