传送门: HDU 5608
附一下tls整理的求积性函数前缀和的姿势, 应该是杜教筛
author: skywalkert original article: http://blog.csdn.net/skywalkert/article/details/50500009 last update time : 2017-04-01
题解:
令 G（n） = n ^ 2 - 3 * n + 2 先反演得:
f(n)=∑d|nG(d)∗μ(nd)
令:
A(n)=∑i=1nf(i) 则:A(n)=∑i=1nf(i)=∑i=1n∑d|iG(d)∗μ(id)
然后从约数角度考虑对A(n)做出的贡献, 得
A(n)=∑i=1n∑d=1⌊ni⌋G(i)∗μ(d)=∑i=1nG(i)∗M⌊ni⌋
其中:
M(n)=∑i=1nμ(i)根据分块可以得到n / i在一段区间内是不变的 一段区间G(i)的和也可以用求和公式直接得到 那么现在就只要求M(n)
1=∑i=1n[i=1]=∑i=1n∑d|iμ(d)=∑i=1n∑d=1⌊ni⌋μ(d)=∑i=1nM(⌊ni⌋)
因此:
M(n)=1−∑i=2nM(⌊ni⌋)同样用分块来做, 可以用线性筛预处理n^(2/3)以内的M(i)
code:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; const int N = 1000001; const int mo = 2333333; const ll mod = 1e9 + 7; bool isPrime[N]; int prime[N]; ll mobius[N]; ll ans; inline ll getG(ll x) {//求和公式 ll mod1 = 6 * mod; ll res = x * (x + 1) % mod1 * (2*x + 1) % mod1 / 6; ll t = 3 * x * (x+1) % (2*mod) / 2; t = mod - t % mod; res = (res + t + x * 2) % mod; return res; } void init() { //预处理M(i) int cnt = 0; memset(isPrime, true, sizeof isPrime); isPrime[1] = false; mobius[1] = 1; // g[1] = 0; for(int i = 2; i < N; ++i) { if(isPrime[i]) { prime[++cnt] = i; mobius[i] = -1; } for(int j = 1; j <= cnt && i * prime[j] < N; ++j) { isPrime[i * prime[j]] = false; if(i % prime[j] == 0) { mobius[i * prime[j]] = 0; break; } mobius[i * prime[j]] = -mobius[i]; } } for(int i = 2; i < N; ++i) { mobius[i] = ((mobius[i] + mobius[i - 1]) % mod + mod) % mod; // g[i] = getG((ll)i); } } ll n; ll v[mo]; ll t[mo]; int last[mo], pre[mo]; int l; void add(int x, ll y, ll z) { t[++l] = y; pre[l] = last[x]; last[x] = l; v[l] = z; } ll getSum(ll R, ll L) { return ((getG(R) - getG(L)) % mod + mod) % mod; } ll cal(ll x) { if(x < N) { return mobius[x]; } int k = x % mo; for(int i = last[k]; i; i = pre[i]) if(t[i] == x) return v[i];//hash做记忆化搜索 ll r; ll ans = 1; for(ll i = 2; i <= x; i = r + 1)//分块 { ll tmp = x / i; r = x / tmp; ll res = cal(tmp) * (r - i + 1) % mod; ans = ((ans - res) % mod + mod) % mod; } add(k, x, ans); return ans; } ll Calc(ll x) { ll ans = 0; ll r; for(ll i = 1; i <= x; i = r + 1) { ll tmp = x / i; r = x / tmp; ll res = cal(tmp) * getSum(r, i - 1) % mod; ans = ((ans + res) % mod + mod) % mod; } return ans; } int main() { init(); int t; cin >> t; while(t--) { cin >> n; ll res = Calc(n); cout << res << endl; } return 0; }