Link

点击打开题目链接

Problem

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

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 σ.

Analyse

这题看到后发现给的变形公式更复杂了,根本没用,所以直接根据定义用Python打表。打表发现,结果为奇数的情况只有x^2和2*x^2两种情况,直接打表最后二分求就行了,注意用long long。

比完赛发现这两种情况可以直接有公式的,因为x^2和2*x^2并没有重复的数值。下面是比赛的代码:

C++ Code

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

const ll maxn = 1e12 + 7;
vector<ll> v;

void init() {
    for(ll i = 1; i*i <= maxn; ++i) {
        v.push_back(i * i);
        if(2 * i * i <= maxn)
            v.push_back(2 * i * i);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

int main() {
    init();
    int T, kase = 0; scanf("%d", &T);
    while(T--) {
        ll x; scanf("%lld", &x);
        ll d = upper_bound(v.begin(), v.end(), x) - v.begin();
        printf("Case %d: %lld\n", ++kase, x - d);
    }
    return 0;
}

欢迎留言