LightOJ - 1336 Sigma Function（规律+数学思维）

传送门

---

题目大意

给出一个数$n$，设其唯一分解式为$n=p_1^{e_1}{p}_2^{e_2}..p_n^{e_n}$，给出$\sigma (n)$定义：

$\sigma (n)=\frac{p_1^{e_1+1}-1}{p_1-1}\ast \frac{p_2^{e_2+1}-1}{p_2-1}\ast ...\ast \frac{p_n^{e_n+1}-1}{p_n-1}$

问$[1,n]$中有多少数的$\sigma$是偶数

解题思路

这题我一开始求出$\sqrt{n}$内的所有质因数，得出每个素数不超过$n$的最大幂次，然后爆搜，但是$TLE$了

首先肯定是手推几个$p,e$看看什么时候为偶数什么时候为奇数，然后不难得出如下结论：

当$p=2$时，无论$e$是多少，这一项只能是奇数当$p$为奇质数时，当且仅当$e$为奇数时这一项才是偶数

因为是若干个奇数偶数相乘，那么只要有一个是偶数最后乘积也一定是偶数。这时对前面一千个数打个表，因为没有贡献的数很少，不难发现如下的数不会贡献答案：$1,2,4,8,9,16,18,25,32,36...$

实际上已经可以看出结果了，也就是只有平方数或者平方数的二倍才不是答案。正确的推理应该是：对于奇质数来说，显然只有所有质数幂次均为偶数最后的结果才为奇数，不难发现这样最后的结果就是奇平方数；考虑$2$后，任何$2$的倍数乘上奇平方数其$\sigma$仍为奇数，那么考虑$2$的奇数次幂和偶数次幂，发现最后的答案实际上就是$n$以内的所有平方数个数和平方数的二倍！

对于$n$以内的平方数个数，类似求$n$以内$k$的倍数个数，只需$\lfloor \sqrt{n}\rfloor$；而平方数的二倍，也就是求$\lfloor \frac{n}{2}\rfloor$内的平方数个数了。

// // Created by Happig on 2020/10/20 // #include <bits/stdc++.h> #include <unordered_map> #include <unordered_set> using namespace std; #define fi first #define se second #define pb push_back #define ins insert #define Vector Point #define ENDL "\n" #define lowbit(x) (x&(-x)) #define mkp(x, y) make_pair(x,y) #define mem(a, x) memset(a,x,sizeof a); typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; const double eps = 1e-8; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double dinf = 1e300; const ll INF = 1e18; const int Mod = 1e9 + 7; const int maxn = 1e6 + 10; /*int prime[maxn], num[maxn]; int cnt, tot; bitset<maxn> vis; ll n, ans; unordered_map<ll, int> mp; void euler() { cnt = 0; for (int i = 2; i < maxn; i++) { if (!vis[i]) { prime[++cnt] = i; } for (int j = 1; j <= cnt && i * prime[j] <= maxn; i++) { vis[i * prime[j]] = 1; if (i % prime[j] == 0) break; } } } void dfs(int d, ll cur = 1) { if (cur > n) return; if (d == tot + 1) { if (!mp.count(cur)) ans++, mp[cur] = 1; return; } if (d == 1) { for (int i = 0; i <= num[d]; i++) { dfs(d + 1, cur); cur *= prime[d]; } } else { for (int i = 0; i <= num[d]; i += 2) { dfs(d + 1, cur); cur *= pow(prime[d], i + 2); } } }*/ int main() { //freopen("in.txt","r",stdin); //freopen("out1.txt", "w", stdout); ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); int T, kase = 0; //euler(); cin >> T; while (T--) { cin >> n; cout << "Case " << ++kase << ": " << n - (int) sqrt(n) - (int) sqrt(n / 2) << endl; // if (n == 3) { // cout << "Case " << ++kase << ": " << 1 << endl; // continue; // } // ans = 0; // int m = sqrt(n + 0.5); // tot = upper_bound(prime + 1, prime + 1 + cnt, m) - prime - 1; // for (int i = 1; i <= tot; i++) { // num[i] = log(n) / log(prime[i]); // } // mp.clear(); // dfs(1, 1); // cout << "Case " << ++kase << ": " << n - ans << endl; } return 0; }