E - Digit Sum Divisible 2

ACM > 题解数学题解构造

发布时间 : 2025-03-16 00:00

妙妙构造题

题目大意：
f(a)：数a 能被它的各个数位的和整除
定义一个数组(a,b)为好的当且仅当
b = a+1
f(a) 且 f(b)

以字符串的形式给定一个数x,(长度小于1e6)

问能否在[x,2x]之间找到一对好数组(a,a+1)
a+1 <= 2x

没有输出-1，有输出任意一个

对于小于1e6可以直接暴力

对于大数则一定有构造方案

数位和为3的倍数的数能被3整除
想到构造2 000

但是不够覆盖所有的[x,2*x]

还有数位和为9的整数必能被9整除
能被8整除只要后三位数能被8整除，所以大数直接往尾巴加0一定可以被8整除

那数位凑齐8可以覆盖[x,2x]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll 

int get(int n) {
    int sum = 0;
    while (n) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    if (s.size() <= 6) {
        int x = stoi(s);
        for (int i = x; i <= 2*x-1; i++) {
            if (i % get(i) == 0 && (i + 1) % get(i+1) == 0) {
                cout << i;
                return 0;
            }
        }
        cout << -1;
        return 0;
    }
    int num = (s[0] - '0') * 10 + s[1] - '0';
    if (num < 17) {
        cout << 17;
    } else if (num < 26) {
        cout << 26;
    } else if (num < 44) {
        cout << 44; 
    } else if (num < 71) {
        cout << 71;
    } else {
        cout << 107;
    }
    for (int i = 2; i < s.size(); i++) {
        cout << 0;
    }
    return 0;
}