这是一篇题解 | 小苯的因子查询

·首先理解一下题意， “给定正整数n,求n!的奇数因数个数占因数总数的分数”。

·所以，要把 n! 的因数全都找出来，我们考虑先分解质因数

·以 5！ = 120 为例子 其分解质因数的结果为 120 = 2³ * 3¹ * 5¹

·因为只有奇数 * 奇数 才会等于奇数 所以我们能知道 120 的奇数因数 只有可能为

1 (3⁰ * 5⁰) 、 3(3¹ * 5⁰) 、 5(3⁰ * 5¹)、 15(3¹ * 5¹)

·发现规律了吗?qwq 所以

(不知道怎么在牛客写Latex公式，就直接截图过来了(

·所以问题就转变为了如何求对应阶乘的2因数个数

·只要一直 /2 到 %2 不为0就行了(记得特判一下0 复杂度O(log(N!))

·现在好像只要预处理一遍阶乘就能过了?

·但是我注意到，对阶乘n!其必然有质因数本质是 (n-1)! 的质因数 * n 的质因数

·所以对 n! 的因数2个数， 也满足这个, 所以我们可以用前缀和预处理的 复杂度O(NlogN)

void init(int n)
{
	S_bary[1] = 0; // 2的因数个数的前缀和
	
	
	for (int i = 2; i <= n; i ++ )
	{
		int num = i;
		int bary = 0, odd = 0;
		while (num && num % 2 == 0) // 一致除到 %2 不为0
		{
			bary ++ ;
			num /= 2;
		} 
		S_bary[i] = (S_bary[i - 1] + bary) % mod; // 前缀和
	}
}

然后最后是要输出 p * q^-1 mod M 到考虑使用经典的乘法逆元

所以乘上q^M-2即可这里因为(a₁ + 1)^-1 为答案,所以输出(a₁ + 1)^{M - 2}

^{用快速幂实现， 复杂度O(logM)}

ll qmi(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1) res = res * a % mod;
		a = a % mod * a % mod;
		b >>= 1;
	}
	return res;
}

·总复杂度O(T(logN + logM)) 能过

·完整AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N = 1000010, mod = 998244353;

int nums[N];
ll S_bary[N];

void init(int n)
{
	S_bary[1] = 0;
	
	
	for (int i = 2; i <= n; i ++ )
	{
		int num = i;
		int bary = 0, odd = 0;
		while (num && num % 2 == 0)
		{
			bary ++ ;
			num /= 2;
		} 
		S_bary[i] = (S_bary[i - 1] + bary) % mod;
	}
}

ll qmi(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1) res = res * a % mod;
		a = a % mod * a % mod;
		b >>= 1;
	}
	return res;
}

int main()
{
	int T;
	scanf("%d", &T);
	int maxv = 0;
	for (int i = 0; i < T; i ++ )
	{
		scanf("%d", &nums[i]);
		if (maxv < nums[i]) maxv = nums[i];
	}
	
	init(maxv);
	
	for (int i = 0; i < T; i ++ )
	{
		printf("%lld ", qmi(S_bary[nums[i]] + 1, mod - 2) % mod);
	}
	
	puts("");
	
	return 0;
} 

·孩子第一次写提解(,欢迎讨论和指出错误

·希望对大伙有所帮助qwq