ZROJ237 小T的gcd - 数论 -

题目链接：http://zhengruioi.com/problem/237

题解：
首先第一问很简单，如果n个数的gcd为1，答案就是 n 否则为 -1
考虑第二问，发现由于 lcm 是小于等于乘积的，若相等则必然两两互质
按照质因数考虑，也就是对于答案区间来说，对于所有的质因数，这个区间至多有一个该质因数的倍数
因此可以从后往前扫一遍，每次分解质因数，然后统计一下上一次出现该质因数是在什么位置，对于位置取min即可
暴力分解大概是略小于\(O(n \sqrt{n})\)，可以有 70pts
这里有一个小 trick：每次分解质因数的时候实际上我只需要知道当前数的最小质因子是什么就行了，这就可以线性筛求出，由于 \(2*3*5*7*11*13*17*19 > 1e6\)，因此时间复杂度为 \(O(8n)\)
当然，注意到当区间左端点左移的时候，区间右端点一定也左移，因此可以双指针扫一下，时间复杂度也是对的

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 1e6+5;

int notpm[maxn], pm[maxn], pcnt = 0, curv[maxn], lea[maxn];

void xxs(){
	notpm[1] = 1;
	for(int i=2;i<=maxn-5;i++){
		if(!notpm[i])pm[++pcnt]=i, curv[i] = pcnt, lea[i] = pcnt;
		for(int j=1;j<=pcnt&&1ll*pm[j]*i<=maxn-5;j++){
			notpm[i*pm[j]] = 1;
			lea[i*pm[j]] = j;
			if(i%pm[j] == 0)break;
		}
	}
}

int n,a[maxn], lst[maxn], rightmost[80005], cs;
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
void solve(){
	int ans = -1;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	int gd = a[1];
	for(int i=2;i<=n;i++)gd=gcd(gd, a[i]);
	memset(rightmost, 0x3f, sizeof rightmost);
	lst[n+1] = n + 1;
	for(int i=n;i>=1;i--){
		lst[i] = lst[i+1];
		int tmp = a[i];
		vector<int>curpm;
		while(tmp != 1){
			curpm.push_back(lea[tmp]);
			int cc = pm[lea[tmp]];
			while(tmp%cc == 0)tmp /= cc;
		}
		for(int u : curpm){
			lst[i] = min(lst[i], rightmost[u]);
			rightmost[u] = i;
		}
		ans = max(ans, lst[i] - i + 1 - 1); 
	}
	printf("Case %d: %d ",++cs,gd == 1 ? n : -1);
	if(ans == 1)puts("-1");
	else printf("%d\n",ans);
}

signed main(){
	xxs();
	int te;scanf("%d",&te);
	while(te--)solve();

	return 0;
}