题解 | 小苯的因子查询

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=998244353,N=1e6+10;
int count2[N];
int ny[N];
int ksm(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1) res=res*a%M;
		a=a*a%M;
		b>>=1;
	}
	return res;
}

void solve()
{
	count2[0]=0;
	for(int i=1;i<N;i++)
	{
		int x=i;
		int count=0;
		while(x%2==0)
		{
			count++;
			x/=2;
		}
		count2[i]=count2[i-1]+count;
	}
	for(int i=0;i<N;i++)
	{
		ny[i]=ksm(count2[i]+1,M-2);
	}
}

signed main()
{
	solve();
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		cout<<ny[n]<<" ";
	}
	
	return 0;
}