https://www.cnblogs.com/violet-acmer/p/10005351.html
题意：
给定一数组a[]，从a[ ]中除去任意个元素得到b[ ]，求能形成多少“好序列”；
好序列的定义是：对于任意的 i 有 b[i]%i == 0（1 ≤ i ≤ size_b[ ]）。
题解：
相关变量解释：
int n;
int a[maxn];
int dp[maxn];//dp[i] : 下标i处可以获得的最大的"好序列"
int factor[maxn];//factor[i] : 记录a[i]的因子
步骤：
(1):从a[1]开始遍历整个数组;
(2):来到a[i]处，将a[i]因式分解，找到其所有的因子factor，并判断其是否在[1,i ]范围内，如果在dp[factor] += dp[factor-1];(对于所有的factor)
具体看代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
const int MOD=1e9+;
const int maxn=1e5+; int n;
int a[maxn];
int dp[maxn];//dp[i] : 下标i处可以获得的最大的"好序列"
int factor[maxn];//factor[i] : 记录a[i]的因子 void updataDp(int i)
{
int index=;
for(int j=;j*j <= a[i];++j)
{
if(a[i]%j == )//判断j是否为a[i]的因子
{
factor[index++]=j;//记录a[i]的因子
if(a[i]/j != j && a[i]/j <= i)//判断其另一个因子a[i]/j是否 <= i，并判断其是否等于 j
factor[index++]=a[i]/j;
}
}
sort(factor+,factor+index);
for(int j=index-;j >= ;--j)//从大因子到小因子，防止a[i]的小因子影响大因子
{
int x=factor[j];
dp[x] += dp[x-];
dp[x] %= MOD;
}
}
int Solve()
{
mem(dp,);
dp[]=;
for(int i=;i <= n;++i)//遍历a[]
updataDp(i);//由a[i]更新dp[] int res=;
for(int i=;i <= n;++i)
res=res%MOD+dp[i]; return res%MOD;
}
int main()
{
scanf("%d",&n);
for(int i=;i <= n;++i)
scanf("%d",a+i);
printf("%d\n",Solve());
}
AC前的错误代码分析：
void updataDp(int i)
{
for(int j=;j < i;++j)
if(a[i]%(j+) == )
dp[j+] += dp[j],dp[j+] %= MOD;
dp[]++;
}
①:从小因子到大因子更新dp[ ],在第五组数据就wa了
根据dp定义，dp[ i ]指的是当前元素a[i]在去点其之前的若干个元素后可以形成的“好序列”个数，终点是“其之前”，如果从小因子到大因子更新dp[ ]，
dp[bigFactor] += dp[bigFactor-1];如果bigFactor-1是a[i]的因子，那么这个因子就会给dp[bigFactor]做贡献，而实际是不需要。
②:查找a[i]的因子是从1遍历到i，在第八组数据TLE
此算法的时间复杂度为O(N^2)，当然会TLE了，然后，实在是没辙了，就去翻了翻大佬博客，发现这篇博客上使用vector存储的a[i]的所有因子，在
查找a[ i ]的所有因子时的时间复杂度是sqrt(n)，当我看到sort排序的时候有点纳闷，加个O(nlogn)的排序难道不超时？
后来仔细想了一下，a[ i ]的所有因子很少(106才49个因子)，所以用sort顶多是O(1)的时间复杂度，而整体时间复杂度为O(n√n)，当然就轻轻松松的A掉了......