HDU 4279-Number(欧拉函数和约数个数的性质)

http://acm.hdu.edu.cn/showproblem.php?pid=4279

题目大意：

定义f(n)为大于1小于n且不是n的约数的数的个数，若f(n)为奇数，则n是一个real number

计算在给定的区间内real number的个数

思路：

首先我们要知道

• 若n > 2，n的欧拉函数值肯定是偶数

• 若n > 2，若n为完全平方数，n的因数个数为奇数，否则n的因数个数为偶数

证明：由基本分解定理可知，任意一个数X都可以分解成质数幂累乘的形式，由计数原理可知

n的因数的个数为所有的幂指数+1的乘积，当且仅当所有的幂指数为偶数时，最终因数的个数

为奇数，否则若存在一个幂指数为奇数，那么加一之后为偶数，相乘的结果也必定是偶数，所

有的幂指数为偶数，那么X必定为一个完全平方数。

首先我们想到，f(n) = n - 约数个数 - 互质数 + 1，因为约数和互质数都减去了1，所以要加回来

接下来我们来分析奇偶性,n > 2时，若n为平方数，f(n) = x - 奇 - 偶 + 1，要使结果为奇数，x为奇

若x不为平方数 f(n) = n - 偶数 - 偶数 + 1，要使结果为奇数，x为偶,最终结果为

奇数平方数 + 偶数非平方数==>为偶数的个数 - 偶数平方的个数 + 奇数平方的个数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f(ll x)
{
if (x <= 2)return 0;
if((ll)sqrt((long double)x) % 2 == 1)//注意转换为long double
return x / 2 + 1 - 2;//若平方开出来的是奇数，说明奇数平方数个数多一个，再减去1和2的情况
else
return x / 2 - 1
- 1;
}
int main()
{
int t;
for (cin >> t; t >= 1; t--) {
ll a, b;
cin >> a >> b;
cout << f(b) - f(a - 1) << endl;
}
return 0;
}

最后

以上就是坚强白羊为你收集整理的HDU 4279-Number(欧拉函数和约数个数的性质)HDU 4279-Number(欧拉函数和约数个数的性质)的全部内容，希望文章能够帮你解决HDU 4279-Number(欧拉函数和约数个数的性质)HDU 4279-Number(欧拉函数和约数个数的性质)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。