筛素数筛了431以内wa了一下午。改成450就过了。
这是wa的代码：

const int N = 500;
const int M = 200;
#define LL  long long

bool is[N];
int prm[M];
LL a[N][M], t;

int getprm(int n){
    int i, j, k = 0;
    int s, e = (int)(sqrt(0.0 + n) + 1);
    memset(is, 1, sizeof(is));
    prm[k++] = 2; is[0] = is[1] = 0;
    for (i = 4; i < n; i += 2) is[i] = 0;
    for (i = 3; i < e; i += 2) if (is[i]) {
        prm[k++] = i;
        for (s = i * 2, j = i * i; j < n; j += s) is[j] = 0;
    }
    for ( ; i < n; i += 2) if (is[i]) prm[k++] = i;
    return k;
}

LL getx(int n, int x) {//非递归写法
    LL ret = 0;
    while (n){
        ret += n/x; n /= x;
    }
    return ret;
}

void init() {

    t = getprm(431); //把这里改成450就过了。
    memset(a, 0, sizeof(a));

    for (int i = 0; i <= 431; i++)
        for (int j = 0; j < t && i >= prm[j]; j++)
            a[i][j] = getx(i, prm[j]);
}


int main() {

    int n, k;
    init();

    while (scanf("%d%d", &n, &k)!=EOF) {

        LL ans = 1;
        for (int i = 0; i < t && n >= prm[i]; i++) {
            LL temp = a[n][i] - a[n - k][i] - a[k][i];
            ans *= (temp + 1);
        }
       printf("%lld\n", ans);

    }

    return 0;
}

• Re:Notice~数据是不是有问题？ (1352) 578141611 2012-07-15 09:45:58
  • Re:Notice~数据是不是有问题？ (8) 578141611 2012-07-15 09:46:23
    • Re:Notice~数据是不是有问题？ (16) 476313260 2012-09-13 20:04:04