「codechefSUBLCM」Subarray LCM

2014年9月24日3,0560

题解

首先筛法求100w以内的素数,同时记录每个质数最小的质因数

然后用last[x]记录质因数x的最后出现位置,用tmp表示max{i}(满足i到当前位置now间的所有数互质)

每次读入一个数a[now],对a[now]分解质因数,更新tmp,更新last[x]

tmp=max(tmp,last[t]);
last[t]=i;

最后用i-tmp更新答案

我表达能力极弱啊。。。

 

avatar
  Subscribe  
提醒