质因子分解表+欧拉筛+埃式筛

模版

质因子分解表

//质因子分解表:线形筛➕最小质因子🟰质因子分解表
void init() {
    vector<int>prime; //质数数组
    for (int i = 2; i <= N; i++) {
        if(!a[i]) { //是质数
            a[i] = i; //只有自己一个因子
            prime.push_back(i);
        }
        for (auto p: prime) {
            if(i*p > N) break; 
            a[i*p] = p; //a数组储存i的最小质数因子
            if(i % p == 0) break; //已经找到最小因子，剩下的交给后面再找
        }
    }
}

vector<int> cal(int x) {
    vector<int>op;
    while(x > 1) {
        int p = a[x];
        op.push_back(p);
        while(x % p == 0) x/=p;
        //依次找到x的每一个最小质数因子
    }return op;
}//x的所有质因子

欧拉筛

void init()
{
    int cnt = 0;
    for (int i = 1; i <= 1000000; i++)  a[i] = 1;
    a[1] = 0;
    for (int i = 2; i <= 1000000; i++)
    {
            if(a[i]==1)b[++cnt] = i;
            for (int j = 1; j <= cnt; j++)
            {
                if (i * b[j] > 1000000)break;
                a[i * b[j]] = 0; //判断这个数不是质数
                if (!(i % b[j]))break; //剩下的数字交给后面判断
            }
        
    }
}

埃式筛

const int N=1e5;
int a[N]; int b[N];
void init()
{
    int cnt = 0;
    for (int i = 2; i <= N; i++)
    {
        if (a[i] == 0) {
            b[cnt++] = i; //是素数
            for (int j = 2; j <= N; j++)
            {
                if (i * j > N) break;
                a[i * j] = 1; //不是素数
            }
        }
    }
    for (int i = 0; i < cnt; i++) cout << b[i] << ' ';
}

例题

<1>（萤火虫难题）

题解：

代码：

#include<iostream>
#include<set>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<string>
#include<string.h>
#include<map>
#include<math.h>

using namespace std;

const int N = 5e5+10;
int n; int c[N];
int w[N];
int cnt = 0;
int a[N],b[N];

//质因子分解表:线形筛➕最小质因子🟰质因子分解表
void init() {
   vector<int>prime;
   for (int i = 2; i <= N; i++) {
       if(!a[i]) {
           a[i] = i;
           prime.push_back(i);
       }
       for (auto p: prime) {
           if(i*p > N) break;
           a[i*p] = p;
           if(i % p == 0) break;
       }
   }
}

struct ty{
   int len;//以数字i结尾的满足条件的最长串
   int col;//数字i的颜色
}r1[N],r2[N];//维护最优和次优的颜色情况

vector<int> cal(int x) {
   vector<int>op;
   while(x > 1) {
       int p = a[x];
       op.push_back(p);
       while(x % p == 0) x/=p;
   }return op;
}//x的所有质因子

signed main() {
   cin >> n; init();
   for (int i = 1; i <= N-5; i++) {
       r1[i] = {0,0};
       r2[i] = {0,0};
   }int ans = 1;

   for (int i = 1; i <= n; i++) {
       cin >> w[i];  //亮度不互质
   }for (int i = 1; i <= n; i++) {
       cin >> c[i];  //颜色不相等
   }

   for (int i = 1; i <= n; i++) {
       auto fs = cal(w[i]);
       int res = 0;

       for (auto p: fs) {
           if(c[i] != r1[p].col) res = max(res,r1[p].len+1);
           else res = max(res,r2[p].len+1);
       }

       ans = max(ans,res);

       for (auto p: fs) {
           if(c[i] == r1[p].col) r1[p].len = max(r1[p].len,res);
           else {
               if(res > r1[p].len) {
                   r2[p].len = r1[p].len;
                   r2[p].col = r1[p].col;
                   r1[p].len = res;
                   r1[p].col = c[i];
               }else if(res > r2[p].len){
                   r2[p].len = res;
                   r2[p].col = c[i];
               }else if(res == r2[p].len) {
                   r2[p].col = 0;
               }
           }
       }
   }cout << ans << endl;
}