筛素数，分解质因数。
代码如下：
1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 8 typedef long long LL; 9 const int N = 444;10 int prm[N >> 2], pn, pid[N], pv[N];11 bool np[N];12 13 void getPrm() {14 np[0] = np[1] = true;15 prm[pn = 0] = 2, pid[2] = pn++;16 for (int i = 3, tmp; i < N; i++, i++) {17 if (!np[i]) prm[pn] = i, pid[i] = pn++;18 for (int j = 0; j < pn; j++) {19 tmp = prm[j] * i;20 if (tmp >= N) break;21 np[tmp] = true;22 if (i % prm[j] == 0) break;23 }24 }25 pv[0] = pv[1] = 1, pv[2] = 2;26 for (int i = 2; i < N; i++, i++) pv[i] = 2;27 for (int i = 3; i < N; i++, i++) {28 if (!pv[i]) {29 for (int j = i; j < N; j += i) pv[j] = i;30 }31 }32 // cout << pn << endl;33 // for (int i = 0; i < 10; i++) cout << prm[i] << endl;34 // for (int i = 0; i < 10; i++) cout << pv[i] << endl;35 }36 37 const int M = 86;38 LL dvs[N][N];39 int tmp[M];40 41 void PRE() {42 getPrm();43 dvs[0][0] = dvs[1][0] = dvs[1][1] = 1;44 for (int i = 2; i < N; i++) {45 for (int j = 0; j < M; j++) tmp[j] = 0;46 dvs[i][0] = 1;47 for (int j = 1; j <= i; j++) {48 int t = i - j + 1;49 while (t > 1) {50 tmp[pid[pv[t]]]++;51 t /= pv[t];52 }53 t = j;54 while (t > 1) {55 tmp[pid[pv[t]]]--;56 t /= pv[t];57 }58 dvs[i][j] = 1;59 for (int k = 0; k < M; k++) dvs[i][j] *= tmp[k] + 1;60 // if (i == 412 && j == 205) { for (int i = 0; i < M; i++) cout << tmp[i] << ' '; cout << endl; cout << dvs[i][j] << endl;}61 }62 }63 // puts("ok~");64 }65 66 int main() {67 int n, m;68 PRE();69 // cout << dvs[10][4] << endl;70 while (~scanf("%d%d", &n, &m)) printf("%lld\n", dvs[n][m]);71 return 0;72 }
——written by Lyon