题解 LightOJ1336 【Sigma Function】

$n=\prod_{i=1}^n p_i^{e_i}$ $o(n)=\prod_{i=1}^n \frac{p_i^{e_i+1}-1}{p_i-1}=\prod_{i=1}^n \sum_{j=0}^{e_i} p_i^j$ 要求$o(n)$为偶数，感觉比较少，考虑$o(n)$为基数的方案数 首先$o(n)$为奇数，说明对于任意的$i$，$\sum_{j=0}^{e_i}p_i^j$为奇数 如果$p_i$为奇数，说明$e_i$为偶数，所以n为平方数 如果$p_i=2$，那么$n \in {x^2,2*x^2}$ 所以和为奇数的数就只有${x^2,2*x^2}$两种可能 代码： ```cpp #include<bits/stdc++.h> #include<iostream> #include<cstdio> #define ll long long using namespace std; ll T,n,Case; int main(){ scanf("%lld",&T); while(T--){ scanf("%lld",&n); printf("Case %lld: %lld\n",++Case,n-(ll)(sqrt(n))-(ll)(sqrt(n/2))); } return 0; } ```