不会 SAM，也不会 SA，原来 SA 还有这种用法。

按 height 从大到小枚举，记当前长度为 $k$，那么把所有 $h_i=k$ 的 $i-1,i$ 所在的并查集合并。
可以证明，如果我们已经合并了 height $\ge k$ 的部分，那么每个连通块的大小就是某个长度为 $k$ 的子串的出现次数。
那么出现次数能被长度整除就只需数出大小为 $k$ 的倍数的联通块数量。

#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int N=1e6+7;
int n,m,cnt[N],rk[N],sa[N],tmp[N],h[N],id[N];
string s;
vector<int>b[N];
int c[N],fa[N],sz[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(nullptr);
	cin>>n>>s;s=' '+s;
	m=300;
	memset(cnt,0,sizeof(int)*(m+1));
	for(int i=1;i<=n;i++)cnt[rk[i]=s[i]]++;
	for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;i--)sa[cnt[rk[i]]--]=i;
	for(int w=1;w<n;w<<=1){
		int p=0;
		for(int i=n-w+1;i<=n;i++)id[++p]=i;
		for(int i=1;i<=n;i++)
			if(sa[i]>w)id[++p]=sa[i]-w;
		memset(cnt,0,sizeof(int)*(m+1));
		for(int i=1;i<=n;i++)cnt[rk[i]]++;
		for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;i--)sa[cnt[rk[id[i]]]--]=id[i];
		m=0;
		for(int i=1;i<=n;i++)
            if(rk[sa[i]]==rk[sa[i-1]]&&rk[sa[i]+w]==rk[sa[i-1]+w])tmp[sa[i]]=m;
            else tmp[sa[i]]=++m;
		memcpy(rk+1,tmp+1,sizeof(int)*n);
	}
	if(n!=1)for(int i=1,k=0;i<=n;i++){
		if(k)k--;
		while(s[sa[rk[i]]+k]==s[sa[rk[i]-1]+k])k++;
		h[rk[i]]=k;
	}
	for(int i=2;i<=n;i++)
		b[h[i]].push_back(i);
	loli ans=0;
	for(int i=1;i<=n;i++)
		fa[i]=i,sz[i]=1;
	c[1]=n;
	for(int k=n;k>=1;k--){
		for(int i:b[k]){
			int x=find(i-1),y=find(i);
			if(x==y)continue;
			c[sz[x]]--;
			c[sz[y]]--;
			fa[y]=x;
			sz[x]+=sz[y];
			c[sz[x]]++;
		}
		for(int j=k;j<=n;j+=k)
			ans+=1ll*j*c[j];
	}
	cout<<ans;
	return 0;
}