Codeforces 264B Good Sequences ★ (分解素因子+DP)

题目链接： http://codeforces.com/problemset/problem/264/B 题目大意：给定一个数列a1,a2,a3,a4,……,an(数据保证ai严格递增,n<=10^5)，求最长的good序列长度：①序列严格递增  ②序列相邻两数不能互素.   题目乍一看好像是nlogn二分+DP的最长上升子序列，但其实这题和LIS一点儿关系都没有……因为数列本身就是严格递增的. 但是此题还需要借鉴LIS的思想，独特的是我们把素因子作为DP的状态，c[pi]表示前面以素数pi为因子的数结尾的最长序列的长度，f[i]表示以第i个数结尾的最长序列的长度。然后我们从左到右扫描序列，每次对当前第i个数分解素因子p1,p2,p3,……pn，找到其中c[pi]最大的，那么我们把此数连到该序列尾便形成了以该数为结尾的最长的good序列。注意完了之后还需要再更新各c[pi]。  

#include 
#include 
#include 
#include 
using namespace std;
#define MAX 100010
int a[MAX],f[MAX],c[MAX];
bool noprime[MAX];
vector  prime;
int gcd(int a, int b){
    return b?gcd(b, a%b):a;
}
void Prime(){
    for (int i = 2; i <= 100000; i ++){
        if (!noprime[i]){
            prime.push_back(i);
        }
        for (int j = 0; j < prime.size() && prime[j] * i <= 100000; j ++){
            noprime[prime[j]*i] = 1;
            if (i % prime[j] == 0)  break;
        }
    }
}
int main(){
    Prime();
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++){
        cin >> a[i];
        int tmp = a[i];
        f[i] = 1;
        for (int j = 0; j < prime.size(); j ++){
            int p = prime[j];
            if (p * p > tmp)
                break;
            if (tmp % p == 0){
                f[i] = max(f[i], c[p] + 1);
                while(tmp % p == 0)
                    tmp /= p;
            }
        }
        if (tmp > 1){
            f[i] = max(f[i], c[tmp] + 1);
        }
        for (int j = 0; j < prime.size(); j ++){
            int p = prime[j];
            if (p * p > a[i])
                break;
            if (a[i] % p == 0){
                c[p] = f[i];
                while(a[i] % p == 0)
                    a[i] /= p;
            }
        }
        if (a[i] > 1){
            c[a[i]] = f[i];
        }
    }

    int maxn = 1;
    for (int i = 0; i < n; i ++)
        if (f[i] > maxn)
            maxn = f[i];
    cout << maxn << endl;
}