只有当 \(x\leq \frac{n}{2}\) 的时候，才满足
\[\sum_{d|x} f_d = 2^x
\]
考场上没注意到这一点，卡了很久。至于为什么有这个限制，是因为当 \(x>\frac{n}{2}\) 的时候，循环节最多重复一次，非常特殊。例如，当 \(n=5,x=3\)，通过 \(2^x\) 来计数，会生成 \(11011\) 这个串，而这个串循环节长度可以是 \(4\) 或 \(5\)，但 \(4\) 和 \(5\) 并不是倍数关系。当 \(x\leq \frac{n}{2}\) 时就不会出现这个问题，详细证明见 Sol。
另外需要预处理一下比较小的 \(f\) ，不然跑不过。
#include<stdio.h>
#include<map>
using namespace std;
inline int read(){
int x=0,flag=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
return flag*x;
}
#define ll long long
const int Mod=998244353;
map<int,ll> mp;
ll qpow(ll x,ll y){
ll ret=1;
while(y){
if(y&1) ret=ret*x%Mod;
x=x*x%Mod,y>>=1;
}
return ret;
}
const int N=1e5+7;
inline ll mod(const ll &x){return x>=Mod? x-Mod:x;}
ll pw[N],f[N];
void init(){
pw[0]=1;
for(int i=1;i<N;i++)
pw[i]=(pw[i-1]<<1)%Mod;
for(int i=1;i<N;i++){
f[i]=mod(f[i]+pw[i]);
for(int j=2;i*j<N;j++)
f[i*j]=mod(f[i*j]+Mod-f[i]);
}
for(int i=1;i<N;i++)
f[i]=mod(f[i]+f[i-1]);
}
ll S(int x){
if(x<N) return f[x];
if(mp[x]) return mp[x];
ll ret=mod(qpow(2ll,x+1)-2+Mod);
for(int l=2,r=0;l<=x;l=r+1){
r=x/(x/l);
ret=mod(ret+Mod-(r-l+1)*S(x/l)%Mod);
}
return mp[x]=ret;
}
int main(){
int T=read(); init();
while(T--){
int n=read(); mp.clear();
ll ans=qpow(2ll,n)-S(n>>1);
for(int l=1,r=0;l<=(n>>1);l=r+1){
r=n/(n/l);
ans=(ans+(S(r)-S(l-1)+Mod)%Mod*(n/l)%Mod)%Mod;
}
printf("%lld\n",ans);
}
}