原题链接 基础数论中很经典的一道题
题意
给出了σ(n)的计算公式，让你找出整数1～n中有多少对应σ(n)的值是偶数.
思路
观察σ(n)的公式发现，每一个乘项都是 (piei+1 - 1) / (pi - 1) 这样，类比等比数列前n项和公式：
(piei+1 - 1) / (pi - 1) = （1 - piei+1) / (1 - pi) = 1 + pi + pi2 + ... + piei
即 σ(n) = ∏(1 + pi + pi2 + ... + piei)
题目要找σ(n)是偶数的值，我们进一步思考如何保证σ(n)是偶数，能否通过上面得到的乘项来确定σ(n)的奇偶性?
我们首先知道奇数运算有一个性质: 做乘法运算时，只有奇数乘奇数才可以的到奇数.
显然利用奇数来讨论会更加容易，我们可以先找到使σ(n)为奇数的情况数，再用总数减去即可得到偶数的情况数.
利用上面的性质可知，若σ(n)是奇数，则每一个乘项(1 + pi + pi2 + ... + piei)必须全为奇数.
因此可做下面的讨论:
从质因子p入手，我们知道任何除2以外的质数都是奇数.
1. 若质因子中不存在 pi = 2，则 pi必为奇数，pi的幂也必为奇数，
要使(1 + pi + pi2 + ... + piei)为奇数，需保证ei为偶数(确保偶数个奇数项相加，再加1及为奇数)
又因为n = p1e1 * p2e2 * ... * pkek，ei是偶数，则n必为一个完全平方数.
2. 若质因子中存在一个 pi = 2，
则pi = 2对应的乘项必为奇数，无论ek是奇数还是偶数.
然后需保证其他所有乘项为奇数.
n = p1e1 * p2e2 * ... * pkek，
若pi = 2对应ek为偶数，则n必为一个完全平方数.
若pi = 2对应ek为奇数，那么n再除以一个2后，n必为完全平方数.
综合以上两种情况后，我们只需统计1～n中所有的完全平方数以及除以2以后是完全平方数的数之和，再用n减去即可得到最终答案.
代码
1 #include <iostream> 2 #include <cmath> 3 using namespace std; 4 typedef long long ll; 5 int main() 6 { 7 int t; 8 cin >> t; 9 for (int i = 1; i <= t; i++) { 10 ll n; 11 cin >> n; 12 ll ans = n; 13 ans -= (ll)sqrt(n) + (ll)sqrt(n / 2.0); 14 printf("Case %d: %lld\n", i, ans); 15 } 16 return 0; 17 }
转载于:https://www.cnblogs.com/AntonLiu/p/10805304.html
