欧拉心算（反演 + 积性函数筛）
歐拉心算
推式子
∑i=1n∑j=1n?(gcd(i,j))=∑d=1n?(d)∑i=1nd∑j=1nd[gcd(i,j)==1]=∑d=1n?(d)∑k=1ndμ(k)(?nkd?)2另t=kd=∑t=1n(?nt?)2∑d∣t?(d)μ(td)另f(n)=∑d∣n?(d)μ(nd)我們考慮如何得到這個函數(shù)的前綴和，顯然這是一個積性函數(shù)有如下性質(zhì)f(1)=1f(p)=?(1)μ(p)+?(p)μ(1)=?1+p?1=p?2否則我們設n=pkt,p,t互質(zhì)f(n)=f(pk)f(t)=(∑d∣pkμ(d)?(pkd))f(t)=(∑i=0kμ(pk)?(pk?i))f(t)=(μ(1)?(pk)+μ(p)?(pk?1))f(t)=(pk?2(p2?2p+1))f(t)由此我們得到了一個線性篩法,接下來數(shù)論分塊即可。\sum_{i = 1} ^{n} \sum_{j = 1} ^{n} \phi(gcd(i, j))\\ = \sum_{d = 1} ^{n} \phi(d) \sum_{i = 1} ^{\frac{n}ze8trgl8bvbq} \sum_{j = 1} ^{\frac{n}ze8trgl8bvbq} [gcd(i, j) == 1]\\ = \sum_{d = 1} ^{n} \phi(d) \sum_{k = 1} ^{\frac{n}ze8trgl8bvbq} \mu(k) (\lfloor \frac{n}{kd}\rfloor) ^2\\ 另t = kd\\ = \sum_{t = 1} ^{n} (\lfloor \frac{n}{t} \rfloor) ^ 2 \sum_{d \mid t} \phi(d) \mu(\frac{t}ze8trgl8bvbq)\\ 另f(n) = \sum_{d \mid n} \phi(d) \mu(\frac{n}ze8trgl8bvbq)\\ 我們考慮如何得到這個函數(shù)的前綴和，顯然這是一個積性函數(shù)有如下性質(zhì)\\ f(1) = 1\\ f(p) = \phi(1) \mu(p) + \phi(p) \mu(1) = -1 + p - 1 = p - 2\\ 否則我們設n = p ^ k t,p, t互質(zhì)\\ f(n) = f(p ^ k) f(t) = (\sum_{d \mid p ^ k} \mu(d) \phi(\frac{p ^ k}ze8trgl8bvbq))f(t)\\ = (\sum_{i = 0} ^{k} \mu(p ^ k) \phi(p ^{k - i}))f(t)\\ = (\mu(1) \phi(p ^ k) + \mu(p) \phi(p ^{k - 1}))f(t)\\ = (p ^{k - 2} (p ^ 2 - 2p + 1))f(t)\\ 由此我們得到了一個線性篩法,接下來數(shù)論分塊即可。 i=1∑n?j=1∑n??(gcd(i,j))=d=1∑n??(d)i=1∑dn??j=1∑dn??[gcd(i,j)==1]=d=1∑n??(d)k=1∑dn??μ(k)(?kdn??)2另t=kd=t=1∑n?(?tn??)2d∣t∑??(d)μ(dt?)另f(n)=d∣n∑??(d)μ(dn?)我們考慮如何得到這個函數(shù)的前綴和，顯然這是一個積性函數(shù)有如下性質(zhì)f(1)=1f(p)=?(1)μ(p)+?(p)μ(1)=?1+p?1=p?2否則我們設n=pkt,p,t互質(zhì)f(n)=f(pk)f(t)=(d∣pk∑?μ(d)?(dpk?))f(t)=(i=0∑k?μ(pk)?(pk?i))f(t)=(μ(1)?(pk)+μ(p)?(pk?1))f(t)=(pk?2(p2?2p+1))f(t)由此我們得到了一個線性篩法,接下來數(shù)論分塊即可。
代碼
bzoj掛了，所以沒地方測試，所以只能在網(wǎng)上找了題解對拍了幾組樣例。
/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h>using namespace std;typedef long long ll;const int inf = 0x3f3f3f3f;const int N = 1e7 + 10;bool st[N];ll f[N], prime[N], cnt;ll quick_pow(ll a, int n) {ll ans = 1;while(n) {if(n & 1) ans = ans * a;a = a * a;n >>= 1;}return ans; }void init() {st[1] = f[1] = 1;for(int i = 2; i < N; i++) {if(!st[i]) {prime[cnt++] = i;f[i] = i - 2;}for(int j = 0; j < cnt && i * prime[j] < N; j++) {st[i * prime[j]] = 1;if(i % prime[j] == 0) {int num = 1, temp = i;while(temp % prime[j] == 0) {temp /= prime[j], num++;}f[i * prime[j]] = 1ll * quick_pow(prime[j], num - 2) * (1ll * prime[j] * prime[j] - 2ll * prime[j] + 1) * f[temp];break;}f[i * prime[j]] = f[i] * f[prime[j]];}}for(int i = 1; i < N; i++) {f[i] += f[i - 1];} }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);init();int T;scanf("%d", &T);while(T--) {ll n, ans = 0;scanf("%lld", &n);for(ll l = 1, r; l <= n; l = r + 1) {r = n / (n / l);ans += (n / l) * (n / l) * (f[r] - f[l - 1]);}printf("%lld\n", ans);}return 0; }總結
以上是生活随笔為你收集整理的欧拉心算（反演 + 积性函数筛）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： c肽是什么
- 下一篇： Polynomial（2019南昌邀请赛