一、基本概念
1. 定义
* 形如 a\sqrt{a}a (a≥0)(a \geq 0)(a≥0) 的式子叫做二次根式
* 其中：
* " \sqrt{\ \ } " 称为二次根号
* aaa 称为被开方数，必须是非负数
2. 有意义条件
* a\sqrt{a}a 有意义 ⇔a≥0\Leftrightarrow a \geq 0⇔a≥0
* 举例：
* x−3\sqrt{x-3}x−3 有意义 ⇒x−3≥0⇒x≥3\Rightarrow x-3 \geq 0 \Rightarrow x \geq 3⇒x−3≥0⇒x≥3
* −5\sqrt{-5}−5 无意义（在实数范围内）
二、重要性质与公式
1. 双重非负性
1. 被开方数非负：a≥0a \geq 0a≥0
2. 结果非负：a≥0\sqrt{a} \geq 0a ≥0
2. 基本公式
* (a)2=a(\sqrt{a})^2 = a(a )2=a (a≥0)(a \geq 0)(a≥0)
* a2=∣a∣={a(a≥0)−a(a<0)\sqrt{a^2} = |a| = \begin{cases} a & (a \geq 0) \\ -a & (a < 0) \end{cases}a2 =∣a∣={a−a (a≥0)(a<0)
3. 运算法则
乘法
a⋅b=ab(a≥0,b≥0)\sqrt{a} \cdot \sqrt{b} = \sqrt{ab} \quad (a \geq 0, b \geq 0) a ⋅b =ab (a≥0,b≥0)
除法
ab=ab(a≥0,b>0)\frac{\sqrt{a}}{\sqrt{b}} = \sqrt{\frac{a}{b}} \quad (a \geq 0, b > 0) b a =ba (a≥0,b>0)
加减法
* 只有同类二次根式才能合并
* 同类二次根式：化简后，被开方数相同的二次根式
* 例：23+53=732\sqrt{3} + 5\sqrt{3} = 7\sqrt{3}23 +53 =73
三、化简与运算
1. 最简二次根式
满足以下三个条件：
1. 被开方数不含分母
2. 被开方数中不含能开得尽方的因数或因式
3. 分母中不含根号
2. 化简方法
根号内因式分解
12=4×3=4×3=23\sqrt{12} = \sqrt{4 \times 3} = \sqrt{4} \times \sqrt{3} = 2\sqrt{3}12 =4×3 =4 ×3 =23
分母有理化
1. 单项分母：1a=aa\dfrac{1}{\sqrt{a}} = \dfrac{\sqrt{a}}{a}a 1 =aa
2. 二项分母：利用平方差公式
* 1a+b=a−ba−b\dfrac{1}{\sqrt{a}+\sqrt{b}} = \dfrac{\sqrt{a}-\sqrt{b}}{a-b}a +b 1 =a−ba −b
* 1a−b=a+ba−b\dfrac{1}{\sqrt{a}-\sqrt{b}} = \dfrac{\sqrt{a}+\sqrt{b}}{a-b}a −b 1 =a−ba +b
四、常见题型与解法
1. 比较大小
* 方法1：平方比较法
* 比较 a\sqrt{a}a 和 b\sqrt{b}b ⇒\Rightarrow⇒ 比较 aaa 和 bbb
* 方法2：作差法
* 方法3：分母有理化后比较
2. 求取值范围
例：x−2+3−x\sqrt{x-2} + \sqrt{3-x}x−2 +3−x 有意义
* 解：{x−2≥03−x≥0⇒2≤x≤3\begin{cases} x-2 \geq 0 \\ 3-x \geq 0 \end{cases} \Rightarrow 2 \leq x \leq 3{x−2≥03−x≥0 ⇒2≤x≤3
3. 整体代入
例：已知 x=3+1x = \sqrt{3} + 1x=3 +1，求 x2−2xx^2 - 2xx2−2x 的值
* 解：x2−2x=(x−1)2−1=(3)2−1=3−1=2x^2 - 2x = (x-1)^2 - 1 = (\sqrt{3})^2 - 1 = 3 - 1 = 2x2−2x=(x−1)2−1=(3 )2−1=3−1=2
五、易错点提醒
1. a2=∣a∣\sqrt{a^2} = |a|a2 =∣a∣，不是 aaa
* (−3)2=3\sqrt{(-3)^2} = 3(−3)2 =3，不是 −3-3−3
2. a⋅b=ab\sqrt{a} \cdot \sqrt{b} = \sqrt{ab}a ⋅b =ab 成立的条件是 a≥0,b≥0a \geq 0, b \geq 0a≥0,b≥0
3. 合并同类项时，系数相加减，根号部分不变
4. 分母有理化时，注意符号不要出错
六、综合例题
例题1：计算
(23+6)(23−6)−(5−2)2(2\sqrt{3} + \sqrt{6})(2\sqrt{3} - \sqrt{6}) - (\sqrt{5} - \sqrt{2})^2 (23 +6 )(23 −6 )−(5 −2 )2
解：
=(23)2−(6)2−[(5)2−210+(2)2]=12−6−(5−210+2)=6−(7−210)=6−7+210=210−1\begin{aligned} &= (2\sqrt{3})^2 - (\sqrt{6})^2 - [( \sqrt{5})^2 - 2\sqrt{10} + (\sqrt{2})^2] \\ &= 12 - 6 - (5 - 2\sqrt{10} + 2) \\ &= 6 - (7 - 2\sqrt{10}) \\ &= 6 - 7 + 2\sqrt{10} \\ &= 2\sqrt{10} - 1 \end{aligned} =(23 )2−(6 )2−[(5
)2−210 +(2 )2]=12−6−(5−210 +2)=6−(7−210 )=6−7+210 =210 −1
例题2：化简求值
已知 a=5−2a = \sqrt{5} - 2a=5 −2，求 a2−1a2−2a+1÷a+1a−1\dfrac{a^2 - 1}{a^2 - 2a + 1} \div \dfrac{a+1}{a-1}a2−2a+1a2−1 ÷a−1a+1 的值
解：
原式=(a−1)(a+1)(a−1)2⋅a−1a+1=1\begin{aligned} \text{原式} &= \frac{(a-1)(a+1)}{(a-1)^2} \cdot \frac{a-1}{a+1} \\ &= 1 \end{aligned} 原式 =(a−1)2(a−1)(a+1) ⋅a+1a−1 =1
（结果与 aaa 的值无关）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目描述
对于正整数 nnn，它的算术平方根 n\sqrt{n}n 可以被化简为 aba\sqrt bab 的形式（a,ba,ba,b 为正整数）。例如 48=212=43\sqrt {48}=2\sqrt{12}=4\sqrt 348 =212 =43 ，(a,b)(a,b)(a,b) 有 (2,12)(2,12)(2,12) 和 (4,3)(4,3)(4,3) 两种可能的取值。我们取其中 bbb 最小的一对 (a,b)(a,b)(a,b)，称 aba\sqrt bab 为 n\sqrt nn 的最简二次根式形式，并记
f(n)=a,g(n)=bf(n)=a,g(n)=bf(n)=a,g(n)=b。例如 434\sqrt 343 是 48\sqrt{48}48 的最简二次根式形式，f(48)=4,g(48)=3f(48)=4,g(48)=3f(48)=4,g(48)=3。
给你一个正整数 NNN，你要求出 F=∏i=1Nf(i)F=\prod_{i=1}^{N} f(i)F=∏i=1N f(i) 和 G=∏i=1Ng(i)G=\prod_{i=1}^{N} g(i)G=∏i=1N g(i)。
答案对 109+710^9+7109+7 取模。
输入格式
本题包含多组测试数据。
输入的第一行包含一个整数 TTT，表示测试数据的组数。
接下来包含 TTT 组数据，每组数据的格式如下：
第一行包含一个正整数 NNN。
输出格式
对于每组测试数据输出一行，包含两个整数 F,GF,GF,G，表示对应的答案。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
说明/提示
样例解释 #1
nnn 111 222 333 444 555 666 777 888 999 101010 n\sqrt{n}n 111 2\sqrt{2}2 3\sqrt{3}3 222 5\sqrt{5}5 6\sqrt{6}6 7\sqrt{7}7 222\sqrt{2}22 333 10\sqrt{10}10 f(n)f(n)f(n) 111 111 111 222 111 111 111 222 333 111 g(n)g(n)g(n) 111 222 333 111 555 666 777 222 111 101010
数据范围
对于所有数据，1≤T≤4001\leq T\leq 4001≤T≤400，1≤N<109+71\leq N<10^9+71≤N<109+7。
测试点编号 NNN 111 ≤400\leq400≤400 222 ≤103\leq10^{3}≤103 333 =5,555=5,555=5,555 444 ≤104\leq10^{4}≤104 555 ≤105\leq10^{5}≤105 666 ≤106\leq10^{6}≤106 777 ≤107\leq10^{7}≤107 888 ≤108\leq10^{8}≤108 999 =1,000,000,006=1,000,000,006=1,000,000,006 101010 ≤1,000,000,006\leq1,000,000,006≤1,000,000,006
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二次根式 / SOSQRT 题解
题目回顾
对于正整数 nnn，我们把 n\sqrt{n}n 写成 aba\sqrt{b}ab 的形式（a,ba,ba,b 为正整数），其中 bbb 最小。这个形式称为最简二次根式，记：
f(n)=a,g(n)=bf(n) = a, \quad g(n) = b f(n)=a,g(n)=b
然后求：
F(N)=∏i=1Nf(i) mod M,G(N)=∏i=1Ng(i) mod MF(N) = \prod_{i=1}^{N} f(i) \bmod M, \quad G(N) = \prod_{i=1}^{N} g(i) \bmod M F(N)=i=1∏N f(i)modM,G(N)=i=1∏N g(i)modM
其中 M=109+7M = 10^9+7M=109+7。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 如何求 F(N),G(N)F(N), G(N)F(N),G(N)
已知 n=ab\sqrt{n} = a\sqrt{b}n =ab ，其中 a,ba, ba,b 是正整数，且 bbb 最小。
我们有：
n=a2×bn = a^2 \times b n=a2×b
并且 bbb 不包含平方因子（square-free，即 bbb 的质因子的指数均为 1）。
因为 bbb 最小意味着 aaa 最大。换句话说，要把 nnn 中所有的平方因子拿出来放进 a2a^2a2 中，剩下的就是 bbb。
设：
n=s2×tn = s^2 \times t n=s2×t
其中 ttt 是平方自由数。那么最简二次根式是：
n=st\sqrt{n} = s \sqrt{t} n =st
所以：
f(n)=s,g(n)=tf(n) = s, \quad g(n) = t f(n)=s,g(n)=t
其中 sss 是最大整数使得 s2∣ns^2 \mid ns2∣n，并且 t=n/s2t = n / s^2t=n/s2 是平方自由的。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 符号定义
定义 s(n)s(n)s(n) 是最大的正整数使得 s(n)2∣ns(n)^2 \mid ns(n)2∣n，记 t(n)=n/s(n)2t(n) = n / s(n)^2t(n)=n/s(n)2 是平方自由部分。
那么：
f(n)=s(n),g(n)=t(n)f(n) = s(n), \quad g(n) = t(n) f(n)=s(n),g(n)=t(n)
因此：
F(N)=∏n=1Ns(n)F(N) = \prod_{n=1}^{N} s(n) F(N)=n=1∏N s(n)
G(N)=∏n=1Nt(n)G(N) = \prod_{n=1}^{N} t(n) G(N)=n=1∏N t(n)
问题转化为：对每个 nnn 分解出它的平方部分 s(n)2s(n)^2s(n)2 和平方自由部分 t(n)t(n)t(n)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 乘积形式
3.1 乘积 F(N)=∏N=1NS(N)F(N) = \PROD_{N=1}^{N} S(N)F(N)=∏N=1N S(N)
设 n=m2×tn = m^2 \times tn=m2×t，其中 ttt 是平方自由数。
那么 s(n)=ms(n) = ms(n)=m。
我们尝试枚举 mmm：
固定 mmm，看哪些 nnn 的 s(n)=ms(n) = ms(n)=m 呢？这要求 m2∣nm^2 \mid nm2∣n，但 nnn 除去 m2m^2m2 后是平方自由数，且 mmm 是最大的满足这个条件的数。
更直接的计数：对于固定的 mmm，n=m2×tn = m^2 \times tn=m2×t，其中 ttt 平方自由，并且 ttt 不能被任何大于 1 的平方数整除（已经平方自由），但这里"最大"意味着：如果 ttt 是平方自由，则 s(n)=ms(n) = ms(n)=m 当且仅当 ttt 不被大于 1 的平方整除（这已经满足），并且 mmm 最大意味着 ttt 与 mmm 没有公共平方因子？其实不对，因为 ttt 平方自由，所以 ttt 与 mmm 没有公共平方因子是自动的，除了 1。
实际上，条件"s(n)=ms(n) = ms(n)=m"等价于：m2∣nm^2 \mid nm2∣n 且 n/m2n/m^2n/m2 平方自由，并且 mmm 是满足 m2∣nm^2 \mid nm2∣n 的最大整数。这个"最大"条件等同于说 n/m2n/m^2n/m2 不被任何大于 1 的平方整除（平方自由）。所以 nnn 在范围 1≤n≤N1 \le n \le N1≤n≤N 内，可以写成 n=m2×tn = m^2 \times tn=m2×t，ttt 平方自由，且 t≤N/m2t \le N/m^2t≤N/m2。
那么 s(n)=ms(n) = ms(n)=m 的个数是：平方自由数的个数 Q(⌊N/m2⌋)Q(\lfloor N/m^2 \rfloor)Q(⌊N/m2⌋)。
这里 Q(x)Q(x)Q(x) 是 111 到 xxx 中平方自由数的个数。
于是：
F(N)=∏m=1⌊N⌋mQ(⌊N/m2⌋)F(N) = \prod_{m=1}^{\lfloor\sqrt{N}\rfloor} m^{Q(\lfloor N/m^2 \rfloor)} F(N)=m=1∏⌊N ⌋ mQ(⌊N/m2⌋)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3.2 乘积 G(N)=∏N=1NT(N)G(N) = \PROD_{N=1}^{N} T(N)G(N)=∏N=1N T(N)
t(n)t(n)t(n) 是 nnn 的平方自由部分。
我们可以换个角度：把 nnn 写成 m2×tm^2 \times tm2×t，对固定的平方自由数 ttt，看它在 1≤n≤N1 \le n \le N1≤n≤N 中出现的次数。
对每个平方自由数 ttt，n=m2×t≤N⇒m≤⌊N/t⌋n = m^2 \times t \le N \Rightarrow m \le \lfloor\sqrt{N/t}\rfloorn=m2×t≤N⇒m≤⌊N/t ⌋。
所以 ttt 在 G(N)G(N)G(N) 的乘积中出现了 ⌊N/t⌋\lfloor\sqrt{N/t}\rfloor⌊N/t ⌋ 次。
那么：
G(N)=∏t=1N, t squarefreet⌊N/t⌋G(N) = \prod_{t=1}^{N, \ t \text{ squarefree}} t^{\lfloor\sqrt{N/t}\rfloor} G(N)=t=1∏N, t squarefree t⌊N/t ⌋
注意 ttt 取到 NNN，但只有平方自由的 ttt 才在乘积中。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 高效计算
我们需要在 NNN 很大（可到 10910^9109 级别）时快速计算。
4.1 计算 F(N)F(N)F(N)
F(N)=∏m=1⌊N⌋mQ(⌊N/m2⌋)F(N) = \prod_{m=1}^{\lfloor\sqrt{N}\rfloor} m^{Q(\lfloor N/m^2 \rfloor)} F(N)=m=1∏⌊N ⌋ mQ(⌊N/m2⌋)
这里 Q(x)Q(x)Q(x) 可以用容斥原理计算：
Q(x)=∑d=1⌊x⌋μ(d)⌊xd2⌋Q(x) = \sum_{d=1}^{\lfloor\sqrt{x}\rfloor} \mu(d) \left\lfloor \frac{x}{d^2} \right\rfloor Q(x)=d=1∑⌊x ⌋ μ(d)⌊d2x ⌋
其中 μ\muμ 是莫比乌斯函数。
这样我们就能快速求 Q(x)Q(x)Q(x) 了。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4.2 计算 G(N)G(N)G(N)
G(N)=∏t=1N, t squarefreet⌊N/t⌋G(N) = \prod_{t=1}^{N, \ t \text{ squarefree}} t^{\lfloor\sqrt{N/t}\rfloor} G(N)=t=1∏N, t squarefree t⌊N/t ⌋
我们可以枚举 k=⌊N/t⌋k = \lfloor\sqrt{N/t}\rfloork=⌊N/t ⌋，它表示某个平方自由数 ttt 对应的指数是 kkk。
即：
设 k=⌊N/t⌋k = \lfloor\sqrt{N/t}\rfloork=⌊N/t ⌋，则 k≤N/t<k+1k \le \sqrt{N/t} < k+1k≤N/t <k+1，即：
N(k+1)2<t≤Nk2\frac{N}{(k+1)^2} < t \le \frac{N}{k^2} (k+1)2N <t≤k2N
并且 ttt 平方自由。
所以对每个 k≥1k \ge 1k≥1，平方自由数 ttt 在区间 (N(k+1)2,Nk2](\frac{N}{(k+1)^2}, \frac{N}{k^2}]((k+1)2N ,k2N ] 内，指数是 kkk。
注意 kkk 最大是 ⌊N⌋\lfloor\sqrt{N}\rfloor⌊N ⌋。
于是：
G(N)=∏k=1⌊N⌋(∏t squarefreeN/(k+1)2<t≤N/k2t)kG(N) = \prod_{k=1}^{\lfloor\sqrt{N}\rfloor} \left( \prod_{\substack{t \text{ squarefree} \\ N/(k+1)^2 < t \le N/k^2}} t \right)^k G(N)=k=1∏⌊N ⌋ t squarefreeN/(k+1)2<t≤N/k2 ∏ t k
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 计算平方自由数乘积
我们需要高效计算：
S(a,b]=∏a<t≤b, t squarefreetS(a,b] = \prod_{a < t \le b, \ t \text{ squarefree}} t S(a,b]=a<t≤b, t squarefree∏ t
即区间 (a,b](a, b](a,b] 内平方自由数的乘积。
利用莫比乌斯函数：
∑t=1t squarefreent=∑d=1⌊n⌋μ(d)d2×sum1(⌊n/d2⌋)\sum_{\substack{t=1 \\ t \text{ squarefree}}}^n t = \sum_{d=1}^{\lfloor\sqrt{n}\rfloor} \mu(d) d^2 \times \text{sum1}(\lfloor n/d^2 \rfloor) t=1t squarefree ∑n t=d=1∑⌊n ⌋ μ(d)d2×sum1(⌊n/d2⌋)
但这是和，我们需要乘积。
乘积可以类似处理，但比较麻烦。一个方法是用前缀乘积的除法，但需要模 MMM 下的逆元。可以预处理平方自由数的前缀乘积，但 nnn 很大时不行。
注意到 nnn 很大，但区间的长度 Nk2−N(k+1)2\frac{N}{k^2} - \frac{N}{(k+1)^2}k2N −(k+1)2N 在 kkk 小时很大，但 kkk 大时很小，不过对 10910^9109 来说直接枚举区间不可行。
必须用数论分块的思想，用 μ(d)\mu(d)μ(d) 来标记平方自由数：
平方自由数的乘积 = 所有数的乘积 / 有平方因子的数的乘积。
有平方因子的数可以通过枚举平方因子来排除。
但更实用的是用莫比乌斯函数：
∏t=1ntμ2(t)=∏d=1n(∏j=1⌊n/d2⌋(jd2)μ(d))\prod_{t=1}^n t^{\mu^2(t)} = \prod_{d=1}^{\sqrt{n}} \left( \prod_{j=1}^{\lfloor n/d^2 \rfloor} (j d^2)^{\mu(d)} \right) t=1∏n tμ2(t)=d=1∏n j=1∏⌊n/d2⌋ (jd2)μ(d)
这个公式有点复杂，但可以做到 O(n)O(\sqrt{n})O(n ) 计算。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 算法步骤
1. 预处理 μ(1)\mu(1)μ(1) 到 μ(⌊N⌋)\mu(\lfloor\sqrt{N}\rfloor)μ(⌊N ⌋)。
2. 对每个 NNN：
* 计算 F(N)F(N)F(N)：
* 枚举 mmm 从 1 到 N\sqrt{N}N ：
* 计算 Q(⌊N/m2⌋)Q(\lfloor N/m^2 \rfloor)Q(⌊N/m2⌋) 用 μ\muμ 求和。
* 累乘 mQ(...) mod Mm^{Q(...)} \bmod MmQ(...)modM。
* 计算 G(N)G(N)G(N)：
* 枚举 kkk 从 1 到 N\sqrt{N}N ：
* 计算区间 L=⌊N/(k+1)2⌋L = \lfloor N/(k+1)^2 \rfloorL=⌊N/(k+1)2⌋，R=⌊N/k2⌋R = \lfloor N/k^2 \rfloorR=⌊N/k2⌋。
* 计算 ∏t=L+1Rtμ2(t)\prod_{t=L+1}^R t^{\mu^2(t)}∏t=L+1R tμ2(t) 用莫比乌斯函数方法。
* 把这个乘积的 kkk 次方乘到答案。
3. 输出 F,GF, GF,G。
时间复杂度大约 O(N)O(\sqrt{N})O(N ) 每组数据，可以过 N≤109N \le 10^9N≤109 的测试。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 核心代码框架（C++）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8. 复杂度与优化
* 筛法 O(NloglogN)O(\sqrt{N} \log \log N)O(N loglogN) 预处理。
* 每次查询 O(NlogN)O(\sqrt{N} \log N)O(N logN) 因为快速幂。
* 可以通过预处理幂来优化，但此框架可以满足题目要求。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
这样就能解决二次根式 这道题了。
