I thought about it for a while after class, and found something.
$$n = \prod_{i = 1} ^ m p_i ^ {a_i}$$
$$f(n) = \sum_{i = 1} ^ m a_i$$
Given $n < 998244353$, how many numbers are there from $1$to $n$, which satisfies $f (I) $even.
With an odd number of $x $and an even number of $y $obviously $x + y = n$, if you can construct a linear combination of $x, y $and easily calculate its value, you can solve the problem.
Just when I studied the sieve, I knew there was such a function:
$$\lambda(n) = (-1) ^ {\sum_{i = 1} ^ m a_I}$$
Consider the meaning of $T = 1_ sum {i = 1} ^ n_ lambda (i) $, that is, between $1 and $n $, the even number minus the odd number, that is, $T = y – x $.
As for $T$, how to use Du screen to calculate the nature of utilization
$$(\lambda \times I)(n) = [n \text{Complete square number] $$
You can.
This question looks very ingenious, but is it really so ingenious?
This question caused me to wonder i f I could find out how many numbers satisfy $f (i) bmod k = 0, 1, 2,…, K – 1 for a given $k $.
I start with analogy.
Assume $x_0, x_1,…, x_{k-1}$, and then construct $k$linear independent combinations between them, and easily calculate the values of these linear combinations.
Observing that the original $k = 2 $, a formula is $1 x + 1 y $, a formula is $1 X – 1 y $, and $1 and $1 $- 1 are both negative roots of the subunit of $2 $, I guess the $i $formula is:
$$(w_k ^ 0) ^ i x_0 + (w_k ^ 1) ^ i x_1 + … + (w_k ^ {k – 1}) ^ i x_{k – 1} = ?$$
It can be regarded as item contribution $(w_k ^ J) ^ i$in $x_j$, re writing.
$$(w_k ^ 0) ^ i x_0 + (w_k ^ 1) ^ i x_1 + … + (w_k ^ {k – 1}) ^ i x_{k – 1} = \sum_{j = 1} ^ n \lambda_i(j)$$
$$\lambda_i(n) = (w_k ^ i) ^ {(f(n) \bmod k)} = w_k ^ {i f(n)}$$
find
$$\lambda_i(p ^ q) = w_k ^ i q$$
$$\lambda_i(p) = w_k ^ i$$
$$\lambda_i(p ^ a q ^ b) = w_k ^ i (a + b) = \lambda_i(p ^ a) \lambda(q ^ b)$$
Everything is ready, $p ^ q$knows, $p$knows, and is integrable function, so direct min_25 sieves.
To sum up, we constructed the $k $formula $(w_k ^ 0) ^ i_x_0 +… (w_k ^{k-1}) ^ I x {k-1} = sum {J = 1} ^ n \ lambda_i (J) $, then you can get the product of $\lambda_i (J) $, then min_25 sieve, then IDFT.
In fact, it’s not so troublesome at all. Consider directly the cyclic polynomial of $k$, prove the product, and take the array directly to min_25 sieve. It is easy to think of a person who does not start from analogy.
What I did was to do DFT once, get the value of DFT by min_25 sieve, and then IDFT.
Anyway, I am too stupid.
I’m not happy to retire. It would be great if I could get the 68 day1t3.