解題區/解題區 - UVa

UVa 995 - Super Divisible Numbers

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

For example, 22203014 is a base-4 super divisible number because 24 is divisible by 1, 224 is divisible by 2, 2224 is divisible by 3, 22204 is divisible by 4, 222034 is divisible by 5, 2220304 is divisible by 6, and 22203014 is divisible by 7.

Find the largest super divisible number of a given base which uses only digits from a given list of digits.

基底為 B 的數字 N 前綴長度 i 必需被 i 整除，找到一個最大符合條件的數字。同時會限用哪幾種 digit。

Sample Input

1
2
4 0123
10 010011

Sample Output

1
2
2220301
10

Solution

感謝天祥大大的指導，一度以為非常多解，因此逼不得以要用 dp 運行，但是仔細想想狀態太大，也無法計算。

根據窮舉的方式可以發現到，每一次窮舉時，假使前一次 mod i = X，則為了要使得 X + ? = 0 (mod i) 則 ? 的地方能填入的數字個數相當於 2 * i <= B 的解，因此答案的數量是相當少的，也就是說最多為 (B/i)! 種可能，撇開不可運行的分枝，其實符合這個條件的數字相當少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h> 
#include <string.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int B, valid[16], path[128];
vector<string> ret[128];
void dfs(int idx) {
    for(int i = idx == 0; i < B; i++) {
        if(!valid[i])	continue;
        path[idx] = i;
        int f = 0;
        for(int j = 0; j <= idx; j++)
            f = (f * B + path[j])%(idx+1);
        if(f == 0) {
            string s = "";
            for(int j = 0; j <= idx; j++)
                s += (path[j] + '0');
            ret[s.length()].push_back(s);
            dfs(idx+1);
        }
    }
}
int main() {
    char s[1024];
    while(scanf("%d %s", &B, &s) == 2) {
        memset(valid, 0, sizeof(valid));
        for(int i = 0; i < 128; i++)
            ret[i].clear();
        for(int i = 0; s[i]; i++)
            valid[s[i]-'0'] = 1;
        dfs(0);
        for(int i = 127; i >= 0; i--) {
            if(ret[i].size()) {
                sort(ret[i].begin(), ret[i].end());
                printf("%s\n", ret[i][ret[i].size()-1].c_str());
                break;
            }
        }
    }
    return 0;
}