题解：P14640 【OIMO Round 1】校验
zyn_
·
·
题解
如此大的数据范围，让我们不得不直面
\sum_{x|n}(-1)^{\Omega(x)}
这和质因子关系很大，设 n=\prod_{i=1}^mp_i^{\alpha_i} 为质因数分解。
由定义，\Omega(n)=\sum_{i=1}^m \alpha_i，(-1)^{\Omega(n)}=(-1)^{\sum_{i=1}^m \alpha_i}=\prod_{i=1}^m(-1)^{\alpha_i}。
枚举 n 的因数 x，可以枚举其每个质因子的幂次。
\sum_{0\le \beta_i\le \alpha_i,i=1,2,\dots,m}(-1)^{\Omega(\prod_{i=1}^m p_i^{\beta_i})}
用一下上面的结论：
\sum_{0\le \beta_i\le \alpha_i,i=1,2,\dots,m}\prod_{i=1}^m(-1)^{\beta_i}
对每个 \beta_i 独立，可以乘法分配律了！
\prod_{i=1}^m\sum_{0\le \beta_i\le \alpha_i}(-1)^{\beta_i}
里面的求和号似乎只能是 0/1 的样子……
\prod_{i=1}^m[2\mid\alpha_i]
根据定义，上式值为 0/1，为 1 当且仅当 n 为平方数。
问题化为，求 [l,r] 中平方数的个数。差分，[1,n] 中有 \lfloor\sqrt{n}\rfloor 个平方数。答案为 \lfloor\sqrt{r}\rfloor-\lfloor\sqrt{l-1}\rfloor。