ural 2047 maths 打表

题目链接戳这里
构造一个长度为n的串，使得除了第一个以外，每个位置的前缀和的因子个数恰好等于该位置上的数。
比如2 4 6 6 4 8 4 8 4 8。前i项和的因子数是a[i]，如前2项和6的因子是a[2]=4；
输入n，输出是这样一个合法的序列a[]。比如:
3 对应 1 3 4；10对应2 4 6 6 4 8 4 8 4 8。

正推很复杂，观察规律。假设所求合法序列的前k项和为S[k]。根据题意有，S[k-1]+A[k]=S[k]，而A[i]=S[k]的因子数，那么S[k-1]=S[k]-A[k]

每个数字的因子数是可以暴力求的。
那么现在若知一个数字S[k]，A[k]总是可知，那么就可以不断逆推出S[k-1]，同理得A[k-1]。题目里Ｎ的最大是1e5，也就是说，我们需要找一个数，使得他能够一直往前推够1e5项。
打表代码为:

#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，则会有1e5项合法的序列。那么题目中，得到n，输出这个序列的前n项即可。

#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;
}