超高速プログラム

目標の石の重さを，元の数（super increasing sequence）における総和に
換算し，それに対して super increasing sequence の性質を利用して解く
プログラム．入力は標準入力から．

（注）石の重さなどの桁数が大きいのでそのままでは普通の計算機では動
      かないかもしれない．

#include <stdio.h>
#include <ctype.h>

#define NUM 10
#define STONES 40
#define MOD 7993823943257
#define INV 308444140027
#define MULT 9826478294024

main()
{   long int slist[STONES+1] = { 0,

    3665308701534, 7330617403068, 506241270389, 2845136891545, 1361758541367,
    70690921978, 804588384145, 196489340090, 1142459568191, 7939847458483,
    6088562083931, 6400576036950, 3637880320065, 1381744556, 3698108030974,
    4727806475348, 6119818214606, 3931881946355, 988458873198, 4929222032268,
    4210741949677, 5384036277020, 5342995695171, 986163840917, 7870495621557, 
    4329276825246, 2347204856362, 2959434526322, 3048315069154, 4949991960816,
    3300216382790, 278119293989, 278784520727, 2817416522030, 5660250136005,
    571646958192, 84846673295, 6191302978762, 6372669810753, 263849911287 };

    long int alist[STONES+1] = { 0,
    2, 4, 9, 19, 40, 96, 188, 493, 873, 1736, 3519, 7109, 14213, 30760,
    59075, 118371, 236509, 473044, 946250, 1894700, 3788289, 7576524,
    15340859, 30492817, 60985502, 121971338, 243954912, 487909051,
    975807645, 1951613959, 3903229585, 7806458726, 15612919563,
    31225838124, 62451686686, 124903366012, 249806726968, 499613471160,
    999229059409, 1998455987473 };

    long int atarget, target, rest;
    int i, j;

    for (i = 1; i <= NUM; i++) {
      scanf("%d", &target);
      atarget = target * INV % MOD;

      printf("No. %2d: target weight = %15d\n"
             ">>> Found Exactly!!\n"
             ">>> Answer:", i, target);

      if (atarget == 0) { printf(" NULL\n\n"); }
      else {
	for (j = STONES; j >= 1;  j--)
	  if (alist[j] <= atarget) break;

	printf(" %d", j);  rest = atarget - alist[j];  j--;

	while (rest > 0) {
	  for (; j >= 1;  j--)
	    if (alist[j] <= rest) break;

	  printf(", %d", j);  rest = rest - alist[j];  j--; }

	printf("\n\n"); } }
}