HDU5608 function

Problem Description
There is a function f(x),which is defined on the natural numbers set N,satisfies the following eqaution

N2−3N+2=∑d|Nf(d)

calulate ∑Ni=1f(i)  mod 109+7.

Input
the first line contains a positive integer T,means the number of the test cases.

next T lines there is a number N

T≤500,N≤109

only 5 test cases has N>106.

Output
Tlines,each line contains a number,means the answer to the i-th test case.

Sample Input
1
3

Sample Output
2

$1^2-3*1+2=f(1)=0$
$2^2-3*2+2=f(2)+f(1)=0->f(2)=0$
$3^2-3*3+2=f(3)+f(1)=2->f(3)=2$
$f(1)+f(2)+f(3)=2$

Source
BestCoder Round #68 (div.2)

Recommend
hujie

简单地套个莫比乌斯反演就行了，最后前缀和用个杜教筛。比较模板，就不详细写了。

<space>
```
#include<cstdio>
#include<cmath>
#include<cstring>
#include<tr1/unordered_map>
#define LL long long
using namespace std;
using namespace tr1;
const int maxn = 5e6 + 5, mod = 1e9 + 7;
int pri[maxn], miu[maxn], M[maxn], t;
unordered_map<LL, LL> hsh;
LL a, b, N, n, ans;
bool vis[maxn];
LL fpow(LL a, LL b, LL c) {
    LL ans = 1;
    while(b) {
        if(b & 1) ans = (ans * a) % c;
        b >>= 1, a = a * a % c;
    }
    return ans;
}
int inv2 = fpow(2, mod - 2, mod), inv6 = fpow(6, mod - 2, mod);
LL Get_2(LL x) {return (((x * (x + 1)) % mod * (2 * x % mod + 1)) % mod * inv6) % mod;}
LL Get(LL x) {return (x * (x + 1) % mod) * inv2 % mod;}
void prime(int N) {
    M[1] = miu[1] = 1;
    for(register int i = 2; i <= N; ++i) {
        if(!vis[i]) pri[++pri[0]] = i, miu[i] = -1;
        for(register int j = 1; j <= pri[0] && i * pri[j] <= N; ++j) {
            vis[i * pri[j]] = 1;
            miu[i * pri[j]] = miu[i] * miu[pri[j]];
            if(i % pri[j] == 0) {
                miu[i * pri[j]] = 0;
                break;
            }
        }
        M[i] = M[i - 1] + miu[i];
    }
}
LL GetMiu(LL x) {
    if(x <= N) return M[x];
    if(hsh[x]) return hsh[x];
    LL ret = 1, l = 2, r = 1, a;
    while(r < x) {
        l = r + 1, r = x / (x / l);
        a = GetMiu(x / l), ret -= (r - l + 1) * a;
        hsh[x / l] = a;
    }
    return ret;
}
int main() {
    scanf("%d", &t);
    N = 5000000;
    prime((int)(N));
    while(t--) {
        scanf("%lld", &n);
        ans = 0;
        for(register LL l = 1, r = 1; l <= n; l = r + 1) {
            r = n / (n / l);
            ans = (ans + (GetMiu(r) - GetMiu(l - 1)) * (Get_2(n / l) - 3 * Get(n / l) + 2 * (n / l)) + mod) % mod;
        }
        printf("%lld\n", (ans + mod) % mod);
    }
    return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链