题目描述
Dpstr学习了动态规划的技巧以后，对数的分解问题十分感兴趣。
Dpstr用此过程将一个正整数x分解成若干个数的乘积：一开始令集合A中只有一个元素x，每次分解时从A中取一个元素a并找出两个大于1且互质的整数p，q，要求pq=a，然后将a分解成两个元素p和q，也就是从A中删去a并加入p和q。Dpstr把正整数x用该过程能分解的次数的最大值称为x的分解数。
例如66的分解数为2，因为最多分解2次。一种分解过程为：一开始A={66}，第1次将66分解为11×6，此时A={11,6}，第2次将6分解为2×3，此时A={11,2,3}，之后无法分解。还可以知道，11，2，3的分解数均为0，因为它们一开始就无法分解。
不过只分解一个数对Dpstr来说不够有趣。Dpstr生成了一个包含n个正整数的数列a1, a2, …, an，请你回答有多少对正整数(l,r)满足1≤l≤r≤n且lcm(al, al+1, …, ar-1, ar)的分解数恰为k。其中lcm(al, al+1, …, ar-1, ar)表示数列从第l项到第r项的所有数的最小公倍数，特别地，当l=r时，lcm(al)=al。由于答案可能很大，只需输出满足条件的正整数对个数除以10,007的余数。
数据范围
对于20%的数据，1≤n≤10，1≤k≤5，1≤ai≤20；
对于40%的数据，1≤n≤100，1≤k≤10，1≤ai≤100；
对于60%的数据，1≤n≤1,000，1≤k≤1,000，1≤ai≤100,000；
对于100%的数据，1≤n≤1,000,000，1≤k≤5,000,000，1≤ai≤10,000,000。
解法
对于i维护极大区间[l,r]使得，[i,l]的lcm的分解数为k，[i,r]的lcm的分解数为k。
那么答案就是所有的i的区间长度。
由于当i右移时，区间[l,r]不可能左移。
所以利用单调性来维护这段区间。
维护一个桶，表示在[i,l]和[i,r]中各个素数的个数，就容易得出一段区间lcm的分解数。
以上维护本身只需O(n)，但分解质因数需要O(n1.5)。
考虑使用线筛优化分解质因数。
使用线筛得出每个数的最小值因子。
那么分解质因数总共只需O(nlogn)
代码
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define ll long long
using namespace std;
const char* fin="dec.in";
const char* fout="dec.out";
const int inf=0x7fffffff;
const int maxn=1000007,maxa=10000007,maxc=664580,mo=10007;
int n,m,i,j,k,l,r;
int a[maxn];
int f[maxa],c[maxc];
int L[maxc],R[maxc];
int p[maxn][9],cnt[maxn][9];
ll ans;
void work(int l){
if (!p[l][0]){
while (a[l]!=1){
if (!p[l][0] || f[a[l]]!=p[l][p[l][0]]){
p[l][++p[l][0]]=f[a[l]];
}
cnt[l][p[l][0]]++;
a[l]/=c[p[l][p[l][0]]];
}
}
}
int main(){
freopen(fin,"r",stdin);
freopen(fout,"w",stdout);
scanf("%d%d",&n,&m);
m++;
f[1]=0;
for (i=2;i<maxa;i++){
if (!f[i]){
c[++c[0]]=i;
f[i]=c[0];
}
for (j=1;j<=c[0];j++){
k=i*c[j];
if (k>=maxa) break;
f[k]=j;
if (i%c[j]==0) break;
}
}
for (i=1;i<=n;i++) scanf("%d",&a[i]);
l=r=0;
for (i=1;i<=n;i++){
while (L[0]<m){
if (l==n){
printf("%lld",ans);
return 0;
}
work(++l);
for (j=1;j<=p[l][0];j++){
L[p[l][j]]+=cnt[l][j];
if (L[p[l][j]]==cnt[l][j]) L[0]++;
}
}
while (r!=n+1 && R[0]<=m){
if (r==n){
r=n+1;
break;
}
work(++r);
for (j=1;j<=p[r][0];j++){
R[p[r][j]]+=cnt[r][j];
if (R[p[r][j]]==cnt[r][j]) R[0]++;
}
}
ans=(ans+r-l)%mo;
for (j=1;j<=p[i][0];j++){
L[p[i][j]]-=cnt[i][j];
if (!L[p[i][j]]) L[0]--;
R[p[i][j]]-=cnt[i][j];
if (!R[p[i][j]]) R[0]--;
}
}
printf("%lld",ans);
return 0;
}启发
这次也是所有区间问题。
之前总结出，所有区间问题可以使用O(nlogn)分治。
但在本题中显然不适用。
目前看来，所有区间问题有如下方法：
1.分治，O(nlogn)
2.动态规划，O(n)
3.维护单调区间，O(n)
线性筛法：分析。
可以用于优化分解质因数。