回复：烂代码，见笑了。
danana
2009-05-12 13:27:25
( reads)
#include
#define NDIGIT 224
int rem[256]; /* stores (10^n % 2009) */
int goal;
int dig[7], cut[7]; /* backtrack states */
int cur_rem, cur_dig; /* for convenience */
int backtrack(int step)
{
int ii, jj; /* ii is current digit, 9-jj is the value for it */
/* goal reached */
if (cur_rem == goal && cur_dig == 0)
{
for (ii = 0; ii printf("%d %d\n", dig[ii], 9-cut[ii]);
return 1;
}
if (step == 7) return 0;
for (ii = step ? dig[step - 1] - 1 : NDIGIT; ii > 0; ii--)
{
for (jj = cur_dig; jj > 0; jj--)
{
dig[step] = ii;
cut[step] = jj;
cur_rem = (cur_rem + rem[ii - 1] * jj) % 2009;
cur_dig -= jj;
if (backtrack(step + 1)) return 1;
cur_rem = (cur_rem - rem[ii - 1] * jj) % 2009;
cur_dig += jj;
}
}
return 0;
}
int main()
{
int ii;
/* initialize rem, rem[i] = (10 ^ i) % 2009 */
for (rem[0] = 1, ii = 1; ii rem[ii] = (rem[ii - 1] * 10) % 2009;
/* now get the remainder of 999999.... (224 9's) % 2009 */
for (goal = 0, ii = 0; ii goal = (goal + rem[ii] * 9) % 2009;
/* now backtrack to match goal by removing a total
* of (224 * 9 - 2009) = 7 from all digits */
cur_rem = 0;
cur_dig = 7;
return !backtrack(0);
}