/** 题目:D - Sigma Function 链接:https://vjudge.net/contest/154246#problem/D 题意:求1~n内约数和为偶数的数的个数。 思路:一个数的约数和为那个数的每个素因子的等比和相乘。如题目所给公式就是等比和化简之后的式子。 那么要判断一个数约数和是否为偶数,可以通过观察它的各个素因子等比和来判断。如果存在某个素因子的等比和为偶数。 那么这个约数和肯定是偶数。否则为奇数。 素因子只有2是偶数,其他都是奇素数。 含素因子2的等比和一定为奇数。其他都是奇素数,只有奇数次方,等比和才是偶数。(未化简之前的式子更好用来判断奇偶) 为了更好处理,求所有奇数约数和的个数。然后总的减去即可得偶数约数和的个数。 奇数约数和: 1,如果素因子不含2,那么肯定是一个平方数。各个素因子次方为偶数。 2,如果素因子含2,那么仍然是与2的若干次方相乘的那个数必须是平方数,他们的乘积是奇数约数和。 于是:假定这里的平方数不再包含2这个素因子。 2^0 * 平方数 为奇数约数和 2^1 * 平方数 2^2 * 平方数 2^3 * 平方数 . . 2^e * 平方数 观察发现。2^2 * 平方数其实已经包含在2^0 * 平方数里面了; 2^3 * 平方数也包含在2^1 *平方数里面了。实质上把2^2转移到那个平方数里面了。 因此只要考虑 一个平方数,以及2*一个平方数 这两种情况都是奇数约数和,且不会重复因为一个2*平方数结果肯定不是平方数。 */ #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6+100; ll n; int main() { int T, cas=1; cin>>T; while(T--) { scanf("%lld",&n); ll ans = (ll)sqrt(n/2)+(ll)sqrt(n);///开根号可能有浮点数误差,有时候要特别处理。 printf("Case %d: %lld ",cas++,n-ans); } return 0; }