题解：AT_arc129_c [ARC129C] Multiple of 7

· · 题解

How

我们发现字符串呈一种多段 7 之间间隔一些数的时候是肯定不劣的。

因为一段长度为 k 的 7 能带来 \frac{k(k+1)}{2} 的贡献，这是平方量级的，通常来说一个小于 10^6 的数最多可以拆分成 5 或 6 段（可以自己跑一遍背包），接下来就是考虑中间间隔的数了。

由于通过同余可以发现在模 7 下，从个位到更高位会有一种循环权值 1,3,2,6,4,5,\cdots 使得这个数每一位乘上它的和模 7 的余数会为这个数的模 7 余数。

那么我们只需要构造每一个间隔的数为其循环权值就可以避免总和会为 7 的倍数（因为最多 6 个间隔）。

其证明同样可以用上述的同余来做，这里不细说（就是类似于前缀和的区别吧，因为每一位对于这个数都会有一个 10^x）。

Code

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define ll long long
#define sjh0626s return
#define code 0
#define int ll
#define gp_hasht __gnu_pbds::gp_hash_table
#define PII pair<int,int>
#define all(v) v.begin(),v.end()
using namespace std;
int T=1,sum,x,cnt,p[6]={1,3,2,6,4,5},bel[6]={6,2,3,1,5,4},pp,n;
stack<int>st;
void solve(){
    cin>>x;
    pp=0;
    while(x){
        sum=0;
        while(sum*(sum+1)/2<=x)++sum;
        x-=sum*(sum-1)/2;
        for(int i=1;i<sum;i++){
            st.push(7);++cnt;
        }
        if(x!=0)st.push(bel[(cnt%6)]),pp++;
        cnt++;
    }
    while(!st.empty()){
        cout<<st.top();st.pop();
    }
}
signed main(){
//  freopen("number.in","r",stdin);
//  freopen("number.out","w",stdout);
//  cin>>T;
    while(T--)solve();
    sjh0626s code;
}