给定一个数N，判定（1-N）中的数P满足gcd(N, P) != 1 && N % P != 0，当一个数在（1-N）中有奇数个这样的数，那么我们就是这个数是可取的，现在要求统计某一个区间[a,b]内有多少个满足要求的数。
一般的思路就是通过区间相减来做了，对于1-N中有多少个这样的可以通过找规律来解决，不管你找没找到，我是没找到...
这题可以来想，对于一个数N，其不互质的数的个数就是 N - phi(N)，在剩余的数里面有多少个数是N的因子呢，通过素因子分解我们知道答案是T = (e1+1)*(e2+1)*...其中e1，e2是素因子的指数，所以最后结果就是 N-phi(N)-T，不过这还有点问题，1这个数在phi(N)计算了一次，在T中又被计算了一次，所以最后结果还要加1，最后结果就是 f(x) = (x - phi(x) - T + 1) % 2，当f(x) = 1，表示这个数是可取的。
然后我们来首先分析phi(x)，我们知道phi(x)是一个积性函数，当A与B互质时，phi(A*B) = phi(A) * phi(B); 那么对x进行素因子分解后有 x = p1^e1 * p2^e2 * ... 我们知道pi^ei 与 pj^ej 是一定互质的，所以也就满足了这个积性函数的要求，phi(x) = phi(p1^e1) * phi(p2^e2)，我们又有phi(p1^e1) = p1^(e1-1)*(p1-1)，除了2以为，所有的数的phi(x)都是一个偶数，这也说明表达式变为：
f(x) = (x - T + 1) % 2 when x ! = 2
f(x) = 0 when x = 2
接了下分析T的结果，由于只要考虑到奇偶性的问题，所以可以得到这个结论，当素因子分解的所有质因子的指数都为偶数的时候，结果为奇数，否则为偶数。
考虑到当x为偶数，x+1为奇数，此时只要T为偶数，那么这个数就是可取的；同理，当x为奇数，x+1为偶数，此时只要T为奇数时，那么这个数也是可取的。从这里我们可以感觉到x为偶数时f(x) = 1的几率是远远大于x为奇数时的，而同时我们注意到x为偶数时不满足的概率也是很小的，那么为偶数时不满足和为奇数时满足的概率有什么关系吗？答案是有的，当一个偶数能够被开根号时（其素因子分解各项指数均为偶数），这个偶数时不可取的，当一个奇数能够被开根号时，这个数就是可取的，因此我们就可以先假设所有的偶数都是满足的，奇数时不满足的，(1, 4分别不符合情况，所以也抵消了)然后通过特殊情况来进行相抵消，于是我们直接对N开根号，如果N是一个奇数的话，那么说明平方数中奇数的个数比偶数多一个，所以在假设的基础上加上一个1，所以最后的答案就是:
(N/2)-2+bool((int) sqrt(N) &1)，其中减去的2分别是2,4这两个不满要求的偶数。
代码如下：
#include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; typedef long long Int64; Int64 a, b, c, d; Int64 get(Int64 x) { Int64 ret = 0; if (x < 6) return ret; ret += x / 2 - 2; // 2,4这两个数不满足要求 if (Int64(sqrt(x)) & 1) { ++ret; } return ret; } int main() { int T; scanf("%d", &T); while (T--) { cin >> a >> b; c = get(a-1); d = get(b); cout << d - c << endl; } return 0; }