# 1. Remoteland (Southwestern Europe Regional Contest 2011)

## Problem

### Description

In the Republic of Remoteland, the people celebrate their independence day every year. However, as it was
a long long time ago, nobody can remember when it was exactly. The only thing people can remember is
that today, the number of days elapsed since their independence (D) is a perfect square, and moreover it is
the largest possible such number one can form as a product of distinct numbers less than or equal to n.
As the years in Remoteland have 1, 000, 000, 007 days, their citizens just need D modulo 1, 000, 000, 007.
Note that they are interested in the largest D, not in the largest D modulo 1, 000, 000, 007.

### Input

Every test case is described by a single line with an integer n, (1 ≤ n ≤ 10, 000, 000). The input ends
with a line containing 0.

### Output

For each test case, output the number of days ago the Republic became independent, modulo 1, 000, 000, 007,one per line.

4
9348095
6297540
0

4
177582252
644064736

# 2. Counting Divisors (2017 多校联合训练第四场 HDOJ 6069)

## Problem

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 3996    Accepted Submission(s): 1450

### Description

In mathematics, the function $d(n)$ denotes the number of divisors of positive integer $n$.
For example, $d(12)=6$ because $1,2,3,4,6,12$ are all $12$’s divisors.
In this problem, given $l,r$ and $k$, your task is to calculate the following thing :
$\left(\sum_{i=l}^r d(i^k)\right)\bmod 998244353$

### Input

The first line of the input contains an integer $T(1\leq T\leq15)$, denoting the number of test cases.
In each test case, there are $3$ integers $l,r,k(1\leq l\leq r\leq 10^{12},r-l\leq 10^6,1\leq k\leq 10^7)$.

### Output

For each test case, print a single line containing an integer, denoting the answer.

## Idea

1. 首先是 唯一分解定理因子个数求法。每个大于 1 的自然数均可写为质数的积，而且这些素因子按大小排列之后，写法仅有一种方式。 其因子的个数为每个质数的幂次 + 1 后的乘积。
比如 $100 = 2^2 \times 5^2$， 其因子的个数即为 $(2+1) \times (2+1) = 9$.
2. 根据 1 我们不难得出一个数字的幂的因子个数， $a = {a_1}^{n_1} \times {a_2}^{n_2}… \times {a_n}^{n_n}$, 则 $a^k$ 因子个数为 $(kn_1+1) \times (kn_2+1)…… \times (ka_n+1)$。如 $100^3$ 的因子个数为 $( (2\times3+1) \times (2 \times 3 +1) )$.
3. 这题我们可以先预先筛出 $\sqrt {r} = 10^6$ 的素数，之后依次用筛出来的每个素数 $p$ 对区间 $p$ 的倍数进行处理，看其因子中有几个 $p$，从而算出区间内每个数因子的个数。进行完前边的处理后，若区间内一个数还有素数因子没处理到，则该素数的幂次为 $1$。具体细节在代码中体现。
4. 区间 $[l,r]$ 内第一个数字 $p$ 的倍数为 $\lfloor {l+p-1 \over p} \rfloor \times p$。

❤采之欲遗谁，所思在远道。❤