Участник:Rimon/Ada and Digits 2

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/ADADIGIT/ C++(gcc 8.3)

#include <iostream>
#include <algorithm>
#include <utility>
#include <cassert>
 
using namespace std;
 
const int MAX = 100005;
const int SIZE = 50000000;
 
int N;
int digits[10];
long long result[2][2];
 
int primeCount;
int was[MAX], primes[MAX], lp[MAX];
int cache0[SIZE];
long long cache1[SIZE];
 
int convert(int *digits) {
    int s = 0;
    for (int i = 0; i < N; i ++) s = 10 * s + digits[i];
    return s;
}
void update(int N, pair<int, long long> &result) {
    if (N < SIZE) {
        cache0[N] = result.first;
        cache1[N] = result.second;
    }
}
pair<int, long long> calculate(int N) {
    if (N < SIZE && cache0[N] != 0) return make_pair(cache0[N], cache1[N]);
    int M = N;
    if (N < MAX) {
        int d = lp[N];
        int _count = 0;
        long long power = d;
        while (N % d == 0) {
            _count ++;
            power *= d;
            N /= d;
        }
        pair<int, long long> get = calculate(N);
        get.first *= _count + 1;
        get.second *= 1LL * (power - 1) / (d - 1);
 
 
        update(M, get);
        return get;
    }
    for (int i = 1; i <= primeCount && primes[i] * primes[i] <= N; i ++) {
        if (N % primes[i] == 0) {
            int d = primes[i];
            int _count = 0;
            long long power = d;
            while (N % d == 0) {
                _count ++;
                power *= d;
                N /= d;
            }
            pair<int, long long> get = calculate(N);
            get.first *= _count + 1;
            get.second *= 1LL * (power - 1) / (d - 1);
            update(M, get);
            return get;
        }
    }
    if (N > 1) {
        pair<int, long long> result = make_pair(2, N + 1);
        if (N < SIZE) update(N, result);
        return result;
    }
    assert(false);
    return make_pair(-1, -1);
}
 
int main() {
    for (int i = 2; i < MAX; i ++) {
        if (was[i]) continue;
        primes[++primeCount] = i;
        for (int j = i; j < MAX; j += i) {
            was[j] = 1;
            lp[j] = i;
        }
    }
 
    cin >> N;
    for (int i = 0; i < N; i ++) cin >> digits[i];
 
    int last = 0;
    sort(digits, digits + N);
    cache0[1] = cache1[1] = 1;
 
    do {
        int current = convert(digits);
        if (current == last) continue;
        last = current;
        pair<int, long long> c = calculate(current);
        if (c.first > result[0][0]) {
            result[0][0] = c.first;
            result[0][1] = current;
        }
        if (c.second > result[1][0]) {
            result[1][0] = c.second;
            result[1][1] = current;
        }
    } while (next_permutation(digits, digits + N));
 
    cout << result[0][1] << " " << result[1][1] << endl;
 
    return 0;
}