Sigma Function LightOJ - 1336 唯一分解定理
题意
约数和 一个数所有约数的和
求从1-n的数中约数和是偶数的数的个数
分析
约数和函数
或者
利用第一个公式
如果因子中有2,则括号中的第一项必为奇数,
除了2之外所有素数都是奇数,所以当p != 2时,
1 + p^1%2+p^2%2+p^3%2+…p^a%2 = a+1(mod 2)
只有当a1,a2,a3,a4(注意不包含有因子2的时候的情况)都是偶数的时候乘积才会是奇数, 于是当 f(n)%2 = 1, n = 2^x*m^2(x =0,1,2,3,4…)
当x为偶数,n = (m*2^(x/2))^2
当x为奇数,n = 2*(m*2^(x/2))^2
又因为唯一分解定理,m^2^(x/2)可以表示所有的整数,翻过来想,所有整数都符合条件,于是 一个整数N,N^2的约数和是奇数,2*N^2的约数和是奇数
由分析可知 N^2这个集合中的元素不可能等于2*N^2这个集合中的元素
于是从1-n所有约数和的为偶数的个数 = sqrt(n)+sqrt(n/2)
参考博客 博客地址
代码参考
int main()
{
int T;
scanf("%d",&T);
int kase = 0;
while(T--)
{
LL n;
scanf("%lld",&n);
LL sum = 0;
sum = n;
sum -= (int)sqrt(n);
sum -= (int)sqrt(n/2);
printf("Case %d: %lld\n",++kase,sum);
}
return 0;
}
不足之处欢迎指正,可随意转载
查看8道真题和解析