先介绍两个：
大数的Gcd
Stein+欧几里德
function stein(a,b:int64):int64;
begin
if a<b then exit(stein(b,a));
if b= then exit(a);
if ((a and )=) and ((b and )=) then exit(stein(a>>,b>>)<<);
if (a and )= then exit(stein(a>>,b));
if (b and )= then exit(stein(a,b>>));
exit(stein((a+b)>>,(a-b)>>));
end;
小数的Gcd
辗转相除法
function stein(a,b:int64):int64;
begin
if a<b then exit(stein(b,a));
if b= then exit(a);
if ((a and )=) and ((b and )=) then exit(stein(a>>,b>>)<<);
if (a and )= then exit(stein(a>>,b));
if (b and )= then exit(stein(a,b>>));
exit(stein((a+b)>>,(a-b)>>));
end;
我们经常要计算到lcm，我们有一个特别优雅的结论
a*b/gcd(a,b)=lcm(a,b)
如此我们只需计算gcd即可，当a,b比较大的时候是一个很好的优化
下面来看一题
题目描述
输入
对于每个测试点：
第一行包括一个整数T，代表数据组数。
对于接下来的每一组数据，包括两行。
第一行，为一个整数N 代表序列长度。
第二行，为用空格分隔的N 个整数Ai，分别代表每一个材料计算好的权值。
输出
对于第i 组数据，你需要输出组数标示“Case i: ” 其中i 表示当前的数据组数。
紧接着，需要输出所要计算的参数α与β，以空格分隔。
如果不存在所要求的子串，对应的参数α或β 设为-1。
样例输入
3
2
7 2
4
2 2 3 4
3
2 2 4
2
7 2
4
2 2 3 4
3
2 2 4
样例输出
Case 1: 2 2
Case 2: 4 2
Case 3: -1 -1
Case 2: 4 2
Case 3: -1 -1
提示
这题大概意思要你分别求两个最长子串，使gcd(al,a2,....,ar)=1 lcm(al,.....ar)=al*....*ar;
gcd好做，读入时不断gcd(a[i],a[i+1])，如果存在gcd(a[i],a[i+1])=1则整串互质，即ans:=n;否则就无解了
第二问Dp做法
f[i]=max(f[i-1]+1,i-k+1); k为最后一个不于ai互质的数的编号。
答案就是max(f[1].....,f[n-1],f[n]);
复杂度O(n)
第二种解法：维护队列
1 维护一个这样的队列使得队列中的数两两互质
2 从左到右依次让元素入队如果队列中一旦不互质，则让队首出队，直到满足两两互质，在这过程中记录元素个数即可