找主位数的最优算法（算法之名整除分块）

找主位数的最优算法（算法之名整除分块）在上述的例子中，就出现了整除的结果相同的情况3/2=3/3=1，这时我们就可以将2和3划分在一起，这就是整除分块的思想。假设N=3，则3/1=3 3/2=1 3/3=1 ps这里整除结果是向下取整https://vjudge.net/problem/HDU-6555 我们分析这道题目，由于数据较大，使用无所不能的暴力求解是不可能的。这道题其实有多种解法，可以使用本文介绍的整除分块，也可以使用玄学打表找规律。 首先我们来介绍一下整除分块。我们可以知道，在整除的过程中会出现相同值的情况。举个栗子：

首先看一道题：

求

是奇数还是偶数。(n<=10^9)

原题链接：

https://vjudge.net/problem/HDU-6555

我们分析这道题目，由于数据较大，使用无所不能的暴力求解是不可能的。这道题其实有多种解法，可以使用本文介绍的整除分块，也可以使用玄学打表找规律。

首先我们来介绍一下整除分块。我们可以知道，在整除的过程中会出现相同值的情况。举个栗子：

假设N=3，则3/1=3 3/2=1 3/3=1 ps这里整除结果是向下取整

在上述的例子中，就出现了整除的结果相同的情况3/2=3/3=1，这时我们就可以将2和3划分在一起，这就是整除分块的思想。

下面对整除分块进行推导证明。