題目連結：https://vjudge.net/problem/LightOJ-1336
1336 - Sigma Function
| PDF (English) | Statistics | Forum |
| Time Limit: 2 second(s) | Memory Limit: 32 MB |
Sigma function is an interesting function in Number Theory. It is denoted by the Greek letter Sigma (σ). This function actually denotes the sum of all divisors of a number. For example σ(24) = 1+2+3+4+6+8+12+24=60. Sigma of small numbers is easy to find but for large numbers it is very difficult to find in a straight forward way. But mathematicians have discovered a formula to find sigma. If the prime power decomposition of an integer is
Then we can write,
For some n the value of σ(n) is odd and for others it is even. Given a value n, you will have to find how many integers from 1 to n have even value of σ.
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 1012).
Output
For each case, print the case number and the result.
| Sample Input | Output for Sample Input |
| 4 3 10 100 1000 | Case 1: 1 Case 2: 5 Case 3: 83 Case 4: 947 |
題意：
求1到n（n<=1e12）内，有多少個數的約數和為偶數。
題解：
1.将一個數n進行質因子分解，得到 pi 和 ai，其中pi為第i個質因子，ai為第i個質因子的個數，
那麼這個數的約數和：f(n) = (1+2^1+2^2……2^a1)*(1+3^1+3^2……3^a2)……*(1+pi^1+pi^2……pi^ai)*……
解釋：從每一個括号中挑選一個數出來相乘，就得到一個約數。在根據組合數的思想，總的就得到所有約數的和。
2.可知：偶數可以是偶數乘以偶數，也可以是奇數乘以偶數；而奇數隻能是奇數乘以奇數。是以，統計奇數要比統計偶數友善，是以總體思想就是用總的個數減去約數和為奇數的個數。
3.那麼，要使 f(n) 為奇數，必須滿足每個括号中的數之和為奇數。可知，當pi = 2時，括号裡的數必定為奇數。因為2的正數次方均為偶數，再加上一個1，就為奇數。是以：
3.1 當n不含有2這個質因子時：每個括号内ai必須為偶數，當ai為偶數就說明了括号内有 ai+1個奇數相加，和為奇數。是以，當每個質因子的個數ai均為偶數時，n可以表示為 n = x^2，即表明當n為一個平方數時，f(n)為奇數。
3.2 當n含有2這個質因子時：可知對于2來說，無論它的個數為多少，對應括号裡的和都為奇數，那麼隻要同時滿足其他括号裡的數之和都為奇數，即滿足3.1的要求，那麼f(n)為奇數。此時 n = 2*x^2。（注：當n = 2*2*2*x^2時， n = 2*(2*x)^2，即同樣滿足 2*x^2的通項公式）
3.3 綜上，當 n = x^2 或者 n = 2*x^2時， f(n)為奇數。是以在n之内，有sqrt(n) + sqrt(n/2) 個數的約數和為奇數。
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #include <vector>
6 #include <cmath>
7 #include <queue>
8 #include <stack>
9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const int INF = 2e9;
15 const LL LNF = 9e18;
16 const int mod = 1e9+7;
17 const int MAXM = 1e5+10;
18 const int MAXN = 5e5+10;
19
20 int main()
21 {
22 int T, kase = 0;
23 scanf("%d", &T);
24 while(T--)
25 {
26 LL n;
27 scanf("%lld",&n);
28 LL ans = n - (LL)sqrt(n) - (LL)sqrt(n/2);
29 printf("Case %d: %lld\n", ++kase,ans);
30 }
31 } View Code