hdu7319 String and GCD

String and GCD

首先我们需要用kmp的fail建树，然后需要利用到欧拉反演。

对于这题来说

那么我们只需要用一个桶存每个约数从根到当前节点出现了多少次。
然后枚举约数也有一个技巧，具体看代码。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<bitset>
#include<vector>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
using namespace std;
typedef long long ll;
const int N=1e6+5;
const ll mo=998244353;
bool vis[N];
int p[N],t[N],f[N],m[N],cnt,g[N];
int to[N],nex[N],head[N],tot,l,r;
char s[N];
int n,j,z;
ll ans;
vector<int> e;
void add(int x,int y){
	to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void work(int x){
	e.clear();
	e.push_back(1);
	while (x!=1){
		z=m[x];
		
		l=0; r=e.size();
		while (x%z==0) {
			x/=z;
			fo(i,l,r-1) e.push_back(e[i]*z);
			l=r; r=e.size();
		}
	}
}
void dfs(int x){
	f[x]=0;
	work(x);
	for (int i=0;i<(int)e.size();i++) {
		f[x]=(f[x]+g[e[i]]*t[e[i]]%mo )%mo;
		t[e[i]]++;
	}
	
	for (int i=head[x];i;i=nex[i]){
		int v=to[i];
		dfs(v);
	}
	
	work(x);
	for (int i=0;i<(int)e.size();i++) {
		t[e[i]]--;
	}
}
int main(){
//	freopen("data.in","r",stdin);

	int size(512<<20); // 512M
	__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
	
	g[1]=1;
	fo(i,2,1e6){
		if (!vis[i]) {
			p[++cnt]=i;
			g[i]=i-1;
			m[i]=i;
		}
		fo(j,1,cnt) {
			if ((ll)i*(ll)p[j]> 1e6) break;
			vis[i*p[j]]=1;
			m[i*p[j]]=p[j];
			
			if (i%p[j]==0) {
				g[i*p[j]]=g[i]*p[j];
				break;
			}
			else{
				g[i*p[j]]=g[i]*(p[j]-1);
			}
		}
	}
	
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%s",s+1);
		n=strlen(s+1);
		
		memset(head,0,sizeof(head));
		memset(p,0,sizeof(p));
		tot=0;
		memset(f,0,sizeof(f));
		
		p[1]=0; j=0;
		fo(i,2,n) {
			while (j && s[j+1]!=s[i]) j=p[j];
			if (s[j+1]==s[i]) j++;
			p[i]=j;
			add(j,i);
		}
		
		fo(i,1,n) if (!p[i]) dfs(i);
		ans=1;
		fo(i,1,n) {
			ans=ans*(f[i]+1)%mo;
//			printf("%d\n",f[i]);
		}	
		printf("%lld\n",ans);
		
	}	
	
	exit(0);
}