題目鏈接戳這里
構(gòu)造一個長度為n的串递惋，使得除了第一個以外，每個位置的前綴和的因子個數(shù)恰好等于該位置上的數(shù)溢陪。
比如2 4 6 6 4 8 4 8 4 8萍虽。前i項和的因子數(shù)是a[i]，如前2項和6的因子是a[2]=4形真；
輸入n杉编，輸出是這樣一個合法的序列a[]。比如:
3 對應(yīng) 1 3 4咆霜；10對應(yīng)2 4 6 6 4 8 4 8 4 8邓馒。
正推很復(fù)雜，觀察規(guī)律裕便。假設(shè)所求合法序列的前k項和為S[k]绒净。根據(jù)題意有见咒，S[k-1]+A[k]=S[k]偿衰，而A[i]=S[k]的因子數(shù)，那么S[k-1]=S[k]-A[k]
每個數(shù)字的因子數(shù)是可以暴力求的。
那么現(xiàn)在若知一個數(shù)字S[k]下翎，A[k]總是可知缤言，那么就可以不斷逆推出S[k-1]，同理得A[k-1]视事。題目里Ｎ的最大是1e5胆萧，也就是說，我們需要找一個數(shù)俐东，使得他能夠一直往前推夠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;
}
