题解：AT_arc129_c [ARC129C] Multiple of 7

laurryble · 2026-07-22 18:58:24 · 题解

介绍一个赛时想到的简单做法。

题意就是让你构造一个能被 7 整除的子串数量为 N 的字符串。

看到这道题时，我先想不如先构造一个全是 7 的满足条件的子串数量不大于 N 的字符串，再逐步改变字符串，减少差值。

后面我在修改字符串时发现由于我们先构造的全是 7，我们改后让只有全是 7 的子串能被 7 整除，这样的话我们就可以把字符串分成几份全是 7 的子串，中间隔开不是 7 的，满足条件的子串数量就是这几份全是 7 的子串每份满足条件子串数量之和。

想到这一点后，我们要构造的字符串就是几份 7 连续段每两段之间夹一个不是 7 的数。我们考虑全是 7 的字符串满足条件的子串数量，发现为 \sum\limits_{i=1}^ni，n 为字符串长度。因为有长度限制，所以我们往每份尽可能多地放 7，直到 N=0。

然后我们考虑在每份间放一个数，使得任意两数与其中间那份组成的数不能被 7 整除，且每个数本身也不能为 7。如何选数呢？由于份数很小，我们把所有情况都枚举出来，看是否符合要求即可。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,cnt,k[1000005],q,fp,mp[1000005][15],p,s[1000005],www[1000005],kx[10][5]={{4},{1,8},{5},{2,9},{6},{3}};
string ans[1000005];
void dfs(int t){
    if(fp) return;
    if(t==p-1){
        int ble=0,flag=0;
        for(int i=1;i<p;i++){
            ble=s[i]%7;
            for(int j=i+1;j<p;j++){
                if(j>i+1) ble=(ble*10+s[j-1])%7;
                for(int l=1;l<=k[j];l++){
                    ble=(ble*10+7)%7;
                }
                if(ble==0){     
                    flag=1;
                    break;
                }
                for(int l=0;l<2;l++){
                    if(s[j]==kx[ble-1][l]){
                        flag=1;
                        break;
                    }
                }
                if(flag) break;     
            }
            if(flag) break;
        }
        if(flag==0){
            fp=1;
            for(int i=1;i<p;i++){
                www[i]=s[i];
                //cout<<s[i]<<" ";
            }
            //cout<<"\n";
            return;
        }
        return;
    }
    for(int i=1;i<=9;i++){
        if(i==7) continue;
        s[++q]=i;
        dfs(t+1);
        q--;
    }
}
signed main(){
    //freopen("number.in","r",stdin);
    //freopen("number.out","w",stdout);
    cin>>n;
    while(n){
        p++;
        cnt=0;
        while(cnt+k[p]+1<=n){
            k[p]++;
            cnt+=k[p];
            ans[p]+='7';
        }
        n-=cnt;
    }
    dfs(0);
    for(int i=1;i<=p;i++){
        cout<<ans[i];
        if(i<p) cout<<www[i];
    }
    return 0;
}