这个算法十分的强... 一般就是用于卡一道数论推结论题最后的(20)~(30)分...
被迫来学习QwQ
算法讲解
这个一般用来筛一个积性函数在(10^{10})左右的前缀和...
为了了解一下,可以看看 2016年国家候选队论文中的任之洲的积性函数求和的几种方法
讲讲一些套路吧...
首先有ymy大佬告诉我的一个神奇东西,这个似乎很有用...
若(f*g=l) ((*)为(Dirichlet)卷积,下同) 若(G)和(L)易求((g,l)的前缀和) 则(F)易求 ((f)的前缀和).
即(displaystyle L(n)-g(1)F(n)=sum _{i=2}^n g(i) F(lfloorfrac{n}{i} floor)). 证明的话可以参照后面的推导来证。
(Dirichlet)卷积 :
定义两个数论函数(f(x),g(x))的(Dirichlet)卷积 (记作((f*g)(x)))
[displaystyle (f*g)(n)=sum _{d|n} f(d)g(frac{n}{d}) ]
引入例题
51nod 1244 莫比乌斯函数之和
题意
求(displaystyle sum _{i=a}^{b} mu(i)). ((2le a le b le 10 ^ {10}))
题解
这道题一个裸的杜教筛...求个前缀和,再减一下就行了...
有一个有用的式子(displaystyle sum _{d|n} mu(d)=[n=1]).(这个可以见我之前那篇博客)
解法一:
直接套用之前那个式子....
(mu * 1=epsilon) 此处(epsilon(x) =[x=1]) 也就是上面那个
右边前缀和都很好求(displaystyle sum _{i=1}^{n} epsilon(i)=1).
然后你代入到之前那个式子就有 (令(displaystyle M(i)=sum_{i=1}^{n} mu(i)))
解法二
我们来手推一下上面的式子qwq
然后就有个很显然的式子(只有(i=1)时候有贡献)
然后更换枚举项,就是考虑每个(d)的对于它倍数的贡献,然后交换和式就行了。
接下来我们就可以提出(i=1)时的一项,也就是(displaystyle sum _{j=1}^{lfloor frac{n}{1} floor=n} mu(j))
我们如果令(displaystyle M(n)=sum_{i=1}^{n} mu(i))就有和之前那个一样的式子了
然后我们对于这个式子就可以递归求解了,时间复杂度是(Theta(n^{frac{2}{3}})).
但是一定要记得要开个哈希表存储一下,不然时间复杂度是个错的!!!(来自ymy大佬的原话)
这个哈希表可以只开(sqrt n)大小,因为(lfloor frac{n}{i} floor)只有这么多种取值.
代码我看了一下fjzzq大佬的博客 emmm... (同届大佬太恐怖了)
我自己写的一个... 注意一定要全程long long
不然有诡异的错误....
代码
#include <bits/stdc++.h>
#define For(i, l, r) for(register ll i = (l), _end_ = (ll)(r); i <= _end_; ++i)
#define Fordown(i, r, l) for(register ll i = (r), _end_ = (ll)(l); i >= _end_; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
typedef long long ll;
bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}
inline ll read() {
ll x = 0, fh = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1;
for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0');
return x * fh;
}
void File() {
#ifdef zjp_shadow
freopen ("1244.in", "r", stdin);
freopen ("1244.out", "w", stdout);
#endif
}
const int N = 2e6 + 1e3;
ll mu[N], Limit, prime[N], cnt;
ll summu[N];
bitset<N> is_prime;
void Mu_Init(int maxn) {
mu[1] = 1; int res; is_prime.set();
is_prime[0] = is_prime[1] = false;
For (i, 2, maxn) {
if (is_prime[i]) { prime[++cnt] = i; mu[i] = -1; }
For (j, 1, maxn) {
res = prime[j] * i;
if (res >= maxn) break ;
is_prime[res] = false;
if (i % prime[j]) mu[res] = -mu[i];
else { mu[res] = 0; break ; }
}
}
For (i, 1, maxn) summu[i] = summu[i - 1] + mu[i];
}
ll Size;
ll p1[N], p2[N], n;
inline ll &App(ll x) { if (x < Size) return p1[x]; return p2[n / x]; }
inline ll Mu_Sum_(ll x) {
if (x <= Limit) return summu[x];
ll &htr = App(x); if (htr != p2[0]) return htr;
ll res = 1, Nextx;
For (i, 2, x) {
Nextx = x / (x / i);
res -= 1ll * (Nextx - i + 1) * Mu_Sum_(x / i);
i = Nextx;
}
return htr = res;
}
inline ll Mu_Sum(ll x) {
Size = (int)(sqrt(x) + 0.5);
Set(p1, -2333); Set(p2, -2333); n = x;
return Mu_Sum_(x);
}
int main () {
File();
ll a, b;
cin >> a >> b;
Limit = N - (int)1e3; Mu_Init(Limit);
cout << Mu_Sum(b) - Mu_Sum(a - 1) << endl;
//cerr << "Time used: " << (double)clock() / CLOCKS_PER_SEC << "s" << endl;
return 0;
}
BZOJ3944 : Sum
然后在简单讲一下求(varphi)(欧拉函数)的前缀和吧...
题意 :
求(displaystyle sum_{i=1}^{n} varphi(i)) 和 (displaystyle sum _{i=1}^{n} mu(i)). ((n le 2^{31}-1))
题解 :
其实和上一道题差不多啦...多求了一个(varphi)嘛...
只要知道(varphi)也有一个类似的结论$$displaystyle sum_{d|n} varphi(d)=n$$
这个我不会证明 只有一个感性理解的方法...(来自具体数学)
你考虑所有分母为(n)的真分数和(frac{n}{n})(共有(n)个)
将分子和分母约去后,其他每个(d|n)的(d)都对它具有(varphi(d))的贡献咯...
例如(n=6).
约分后就是
这个就比较显然了, 应该可以写出证明的...(太懒也太菜了..)
然后像上一题一样的啦~ 上道题两个解法都能用用...
(varphi * 1=id) ((id(x)=x)) 我们令(displaystyle phi(n) = sum _ {i=1}^{n} varphi(i)).
就有一个显然的式子
这个同上就行咯...
hihoCoder #1456 : Rikka with Lattice
这题也是一道好题!~
如果想看的,就在我另一篇博客上 无耻骗点击...