CodeForces 376C – Divisible by Seven

点击打开codeforces题目链接

题意

给你一个不长于10^6个数字的数,其中肯定包含1,6,8,9这几个数字,现在让你重新排列这些数字,使得这个数能够被7整除

分析

1,6,8,9这几个数字的各种排列能够凑出模为0~6的数,那么只需要前面使用所有其他的数字,最后补上1689即可

C++代码

#include <bits/stdc++.h>
using namespace std;

vector<int> t = { 1869,6198,1896,1689,1986,1968,1698 };
int cnt[12];

bool check() {
    for(int i = 0; i < 12; ++i)
        if(i==1 || i==6 || i==8 || i==9) {
            if(cnt[i] <= 0) return false;
            --cnt[i];
        }
    return true;
}

int main() {
    string num; cin >> num;
    for(int i = 0; i < num.size(); ++i)
        ++cnt[num[i]-'0'];
    if(!check()) { puts("0"); return 0; }
    int mod = 0;
    for(int i = 1; i <= 9; ++i) {
        while(cnt[i]-- > 0) {
            printf("%d", i);
            mod = (mod * 10 + i) % 7;
        }
    }
    printf("%d", t[mod]);
    while(cnt[0]-- > 0)
        printf("0");
    printf("\n");
    return 0;
}

欢迎留言