Preventing Alzheimer's

/*
 Petar 'PetarV' Velickovic
 Task: Preventing Alzheimer's
*/

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <complex>

#define DPRINTC(C) printf(#C " = %c\n", (C))
#define DPRINTS(S) printf(#S " = %s\n", (S))
#define DPRINTD(D) printf(#D " = %d\n", (D))
#define DPRINTLLD(LLD) printf(#LLD " = %lld\n", (LLD))
#define DPRINTLF(LF) printf(#LF " = %.5lf\n", (LF))

using namespace std;
typedef long long lld;
typedef unsigned long long llu;

int t;
int n, k;
int a[25];
int fin[25];
int origSum;
int sol;

int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311};
lld masks[313];

lld getMask(int x)
{
    lld ret = 0LL;
    for (int i=0;i < 64 && primes[i] <= x; i++)
    {
        if (x % primes[i] == 0) ret |= (1LL << i);
    }
    return ret;
}

inline int max1(int a, int b)
{
    if (a > b) return a;
    return b;
}

void solve(int ind, int currSum, int prevNum, lld mask)
{
    if (ind == n)
    {
        if (currSum < sol) sol = currSum;
        return;
    }

    /* //DEBUG
     printf("Recursing.\n");
     DPRINTD(ind);
     DPRINTD(currSum);
     DPRINTD(prevNum);
     printf("------------\n");
    */

    int remNumbers = n - ind - 1;
    int minNext = a[ind] / k;
    if (a[ind] % k != 0) minNext++;
    for (int i=max1(minNext , prevNum + 1);;i++)
    {
        if (currSum + k*(i + remNumbers*i + remNumbers*(remNumbers+1)/2) >= sol) return;
        lld newMask = masks[i];
        if (mask & newMask) continue;
        solve(ind+1, currSum + k*i, i, (mask | newMask));
    }
}

int main()
{
    freopen("/Users/PetarV/preventing_alzheimers.txt","r",stdin);
    freopen("/Users/PetarV/HackerCup/alzheimers_out.txt","w",stdout);


    for (int num=2;num<=312;num++)
    {
        masks[num] = getMask(num);
    }

    scanf("%d",&t);
    for (int f=1;f<=t;f++)
    {
        scanf("%d%d",&n,&k);
        origSum = 0;
        for (int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            origSum += a[i];
        }

        sort(a, a+n);

        sol = 987654321;
        if (a[n-1] <= k)
        {
            sol = k * n;
            if (a[0] == 0) sol -= k;
            sol -= origSum;
        }
        else
        {
            int ii = 0;
            while (a[ii] <= k)
            {
                fin[ii] = k;
                ii++;
            }
            /* sfprtstpshr */
            int prevII = ii;
            int curr = k*ii;
            int jj = 0;
            for (; ii < n; ii++)
            {
                int xx = k * primes[jj];
                while (a[ii] > xx)
                {
                    jj++;
                    xx = k * primes[jj];
                }
                fin[ii] = xx;
                jj++;
            }
            sol = 0;
            for (int i=0;i<n;i++) sol += fin[i];
            solve(prevII, curr, 1, 0LL);
            sol -= origSum;
        }

        printf("Case #%d: %d\n", f, sol);
    }
    return 0;
}