首页 > 代码库 > CC Subarray LCM （数学）
CC Subarray LCM （数学）
题目连接：http://www.codechef.com/problems/SUBLCM
题意：给定一个序列，求最长连续子序列满足 LCM(Ai,Ai+1...Aj) =Ai*Ai+1*...*Aj。
分析：若要满足 LCM(Ai,Ai+1...Aj) =Ai*Ai+1*...*Aj，必须子序列内两两互质（没有相同质因子），因此首先筛素因子。
由dp[i]表示从a[i]开始往回走，最远到达pos还满足 LCM(Apos,Ai+1...Ai) =Apos*Apos+1*...*Ai ，则dp[i]取决于dp[i-1]和之前有没有最右出现a[i]含有的质因子。
用一个数组记录每个质因子最右出现的位置，则dp[i]=max(dp[i-1],last)（last表示a[i]含有的质因子出现最右的位置）
最后ans=max(ans,i-dp[i]+1)即可。
#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define N 1000010#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;vector<int>PrimeFactor[N];int prime[N];int gcd(int a,int b){ return a%b==0?b:gcd(b,a%b);}void init(){ for(int i=2;i<N;i++)//筛素因子 { if(!prime[i]) { for(int j=i;j<N;j+=i) PrimeFactor[j].push_back(i),prime[j]=1; } }}int pos[N],dp[N],a[N];int main(){ init(); int T,n,x; scanf("%d",&T); while(T--) { scanf("%d",&n); FILL(pos,0); int ans=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); x=a[i]; int maxlast=0; for(int j=0,sz=PrimeFactor[x].size();j<sz;j++)//找出a[i]含有的质因子最右位置 { int factor=PrimeFactor[x][j]; maxlast=max(maxlast,pos[factor]+1); pos[factor]=i; } if(i>1&&gcd(a[i],a[i-1])!=1) { dp[i]=i;continue; } dp[i]=max(maxlast,dp[i-1]); } for(int i=1;i<=n;i++)ans=max(ans,i-dp[i]+1); if(ans<=1)ans=-1; printf("%d\n",ans); }}
CC Subarray LCM （数学）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。