題目鏈接戳這里
構(gòu)造一個(gè)長(zhǎng)度為n的串，使得除了第一個(gè)以外，每個(gè)位置的前綴和的因子個(gè)數(shù)恰好等于該位置上的數(shù)。
比如2 4 6 6 4 8 4 8 4 8。前i項(xiàng)和的因子數(shù)是a[i]，如前2項(xiàng)和6的因子是a[2]=4；
輸入n，輸出是這樣一個(gè)合法的序列a[]。比如:
3 對(duì)應(yīng) 1 3 4；10對(duì)應(yīng)2 4 6 6 4 8 4 8 4 8。

正推很復(fù)雜，觀察規(guī)律。假設(shè)所求合法序列的前k項(xiàng)和為S[k]。根據(jù)題意有，S[k-1]+A[k]=S[k]，而A[i]=S[k]的因子數(shù)，那么S[k-1]=S[k]-A[k]

每個(gè)數(shù)字的因子數(shù)是可以暴力求的。
那么現(xiàn)在若知一個(gè)數(shù)字S[k]，A[k]總是可知，那么就可以不斷逆推出S[k-1]，同理得A[k-1]。題目里Ｎ的最大是1e5，也就是說(shuō)，我們需要找一個(gè)數(shù)，使得他能夠一直往前推夠1e5項(xiàng)。
打表代碼為:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define RFOR(i,a,b) for(ll i=(b-1);i>=a;--i)

const int maxN=2e6;
int F[maxN + 5], dp[maxN];

void get_factor() {
  memset(F, 0, sizeof F);
  FOR(i, 1, maxN + 1)
    for (int j = i; j <= maxN; j += i)
      ++F[j];
}

void solve() {
  memset(dp, 0, sizeof dp);
  dp[1] = dp[2] = 1;
  FOR(i, 3, maxN + 1) {
    int f = F[i];
    dp[i] = dp[i - f] + 1;
    if (dp[i] >= 1e5) {
      cout << i << " " << dp[i] << endl;
      break;
    }
  }
}

int main() {
  get_factor();
  solve();
  return 0;
}

得到，若S[k]=1568617，則會(huì)有1e5項(xiàng)合法的序列。那么題目中，得到n，輸出這個(gè)序列的前n項(xiàng)即可。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
const int maxN = 1e5 + 5;
int N, M, K;

const int T = 1568617;
int ans[maxN];
int fact[T + 1], d;

void getFact() {
    mst(fact, 0);
    for (int i = 1; i <= T; ++i)
        for (int j = i; j <= T; j += i)
            ++fact[j];

    int x = T;
    d = 0;
    while (x) {
        ans[d++] = x;
        int num = fact[x];
        x -= num;
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif
    getFact();
    scanf("%d", &N);
    int sum = 0;
    for (int i = d - 1, j = 1; j <= N; ++j, --i) {
        if (j != 1) printf(" ");
        printf("%d", ans[i] - sum);
        sum = ans[i];
    }
    return 0;
}