hdu7319 String and GCD
String and GCD
首先我们需要用kmp的fail建树，然后需要利用到欧拉反演。
\[n=\sum_{d|n} \varphi(d)
\]
对于这题来说
\[(i,j)=\sum_{d|(i,j)} \varphi(d)=\sum_{d|i,d|j} \varphi(d)
\]
那么我们只需要用一个桶存每个约数从根到当前节点出现了多少次。
然后枚举约数也有一个技巧，具体看代码。
#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);
}