网站可以用ai做吗,南京建设工程管理局网站,小规模企业所得税怎么算,百度平台推广欧拉心算
推式子 ∑i1n∑j1nϕ(gcd(i,j))∑d1nϕ(d)∑i1nd∑j1nd[gcd(i,j)1]∑d1nϕ(d)∑k1ndμ(k)(⌊nkd⌋)2另tkd∑t1n(⌊nt⌋)2∑d∣tϕ(d)μ(td)另f(n)∑d∣nϕ(d)μ(nd)我们考虑如何得到这个函数的前缀和#xff0c;显然这是一个积性函数有如下性质f(1)1f(p)ϕ(1)μ(p)ϕ…欧拉心算
推式子
∑i1n∑j1nϕ(gcd(i,j))∑d1nϕ(d)∑i1nd∑j1nd[gcd(i,j)1]∑d1nϕ(d)∑k1ndμ(k)(⌊nkd⌋)2另tkd∑t1n(⌊nt⌋)2∑d∣tϕ(d)μ(td)另f(n)∑d∣nϕ(d)μ(nd)我们考虑如何得到这个函数的前缀和显然这是一个积性函数有如下性质f(1)1f(p)ϕ(1)μ(p)ϕ(p)μ(1)−1p−1p−2否则我们设npkt,p,t互质f(n)f(pk)f(t)(∑d∣pkμ(d)ϕ(pkd))f(t)(∑i0kμ(pk)ϕ(pk−i))f(t)(μ(1)ϕ(pk)μ(p)ϕ(pk−1))f(t)(pk−2(p2−2p1))f(t)由此我们得到了一个线性筛法,接下来数论分块即可。\sum_{i 1} ^{n} \sum_{j 1} ^{n} \phi(gcd(i, j))\\ \sum_{d 1} ^{n} \phi(d) \sum_{i 1} ^{\frac{n}{d}} \sum_{j 1} ^{\frac{n}{d}} [gcd(i, j) 1]\\ \sum_{d 1} ^{n} \phi(d) \sum_{k 1} ^{\frac{n}{d}} \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}{d})\\ 另f(n) \sum_{d \mid n} \phi(d) \mu(\frac{n}{d})\\ 我们考虑如何得到这个函数的前缀和显然这是一个积性函数有如下性质\\ f(1) 1\\ f(p) \phi(1) \mu(p) \phi(p) \mu(1) -1 p - 1 p - 2\\ 否则我们设n p ^ k t,p, t互质\\ f(n) f(p ^ k) f(t) (\sum_{d \mid p ^ k} \mu(d) \phi(\frac{p ^ k}{d}))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)\\ 由此我们得到了一个线性筛法,接下来数论分块即可。 i1∑nj1∑nϕ(gcd(i,j))d1∑nϕ(d)i1∑dnj1∑dn[gcd(i,j)1]d1∑nϕ(d)k1∑dnμ(k)(⌊kdn⌋)2另tkdt1∑n(⌊tn⌋)2d∣t∑ϕ(d)μ(dt)另f(n)d∣n∑ϕ(d)μ(dn)我们考虑如何得到这个函数的前缀和显然这是一个积性函数有如下性质f(1)1f(p)ϕ(1)μ(p)ϕ(p)μ(1)−1p−1p−2否则我们设npkt,p,t互质f(n)f(pk)f(t)(d∣pk∑μ(d)ϕ(dpk))f(t)(i0∑kμ(pk)ϕ(pk−i))f(t)(μ(1)ϕ(pk)μ(p)ϕ(pk−1))f(t)(pk−2(p2−2p1))f(t)由此我们得到了一个线性筛法,接下来数论分块即可。
代码
bzoj挂了所以没地方测试所以只能在网上找了题解对拍了几组样例。
/*Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include bits/stdc.husing 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;
}
