bzoj4804: 欧拉心算

题目链接
给 出 n ， 计 算 ∑ i = 1 n ∑ j = 1 n φ ( gcd ⁡ ( i , j ) ) 给出n，计算\sum_{i=1}^n\sum_{j=1}^n\varphi(\gcd(i,j)) 给出n，计算i=1∑n​j=1∑n​φ(gcd(i,j))
f ( n ) = ∑ i = 1 n ∑ j = 1 n φ ( gcd ⁡ ( i , j ) ) = ∑ d = 1 n φ ( d ) ∑ i = 1 ⌊ n d ⌋ ∑ j = 1 ⌊ n d ⌋ ∑ k ∣ gcd ⁡ ( i , j ) μ ( k ) = ∑ d = 1 n φ ( d ) ∑ k = 1 ⌊ n d ⌋ ⌊ n d k ⌋ 2 μ ( k ) f(n)=\sum_{i=1}^n\sum_{j=1}^n\varphi(\gcd(i,j)) =\sum_{d=1}^n\varphi(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{k|\gcd(i,j)}\mu(k) =\sum_{d=1}^n\varphi(d)\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{dk}\rfloor^2\mu(k) f(n)=i=1∑n​j=1∑n​φ(gcd(i,j))=d=1∑n​φ(d)i=1∑⌊dn​⌋​j=1∑⌊dn​⌋​k∣gcd(i,j)∑​μ(k)=d=1∑n​φ(d)k=1∑⌊dn​⌋​⌊dkn​⌋2μ(k)
令 T = d k ， 则 f ( n ) = ∑ T = 1 n ⌊ n T ⌋ 2 ∑ d ∣ T φ ( d ) μ ( T d ) 令T=dk，则f(n)=\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor^2\sum_{d|T}\varphi(d)\mu(\frac{T}{d}) 令T=dk，则f(n)=T=1∑n​⌊Tn​⌋2d∣T∑​φ(d)μ(dT​)
令 g ( T ) = ∑ d ∣ T φ ( d ) μ ( T d ) ， 易 知 g ( T ) 是 积 性 函 数 令g(T)=\sum_{d|T}\varphi(d)\mu(\frac{T}{d})，易知g(T)是积性函数 令g(T)=d∣T∑​φ(d)μ(dT​)，易知g(T)是积性函数
设 T = ∏ i = 1 t p i a i , 其 中 p i 为 互 不 相 等 的 质 数 则 g ( T ) = ∏ i = 1 t g ( p i a i ) = ∏ i = 1 t ( μ ( 1 ) φ ( p i a i ) + μ ( p i ) φ ( p i a i − 1 ) ) = ∏ i = 1 t ( φ ( p i a i ) − φ ( p i a i − 1 ) ) 设T=\prod_{i=1}^{t}p_i^{a_i},其中p_i为互不相等的质数\\ 则g(T)=\prod_{i=1}^{t}g(p_i^{a_i}) =\prod_{i=1}^{t}(\mu(1)\varphi(p_i^{a_i})+\mu(p_i)\varphi(p_i^{a_i-1})) =\prod_{i=1}^{t}(\varphi(p_i^{a_i})-\varphi(p_i^{a_i-1})) 设T=i=1∏t​piai​​,其中pi​为互不相等的质数则g(T)=i=1∏t​g(piai​​)=i=1∏t​(μ(1)φ(piai​​)+μ(pi​)φ(piai​−1​))=i=1∏t​(φ(piai​​)−φ(piai​−1​))
线性筛出$g(T)$及其前缀和，最后分块计算$f(n)$。

#include 
#include 
#include 
#include 
#include 
using namespace std;typedef long long ll;
const int N = 10000010, maxn = 10000000;char buf;
inline int read() {register int rst = 0;do buf = getchar(); while (! isdigit(buf));while (isdigit(buf)) rst = rst*10 + buf - '0', buf = getchar();return rst;
}int T, n;
ll g[N];//80MB
bool isNotPrime[N];
vector<int> ls;inline void init() {g[1] = 1;for (int i = 2; i <= maxn; i++) {if (! isNotPrime[i]) {ls.push_back(i), g[i] = i - 2;}for (vector<int>::iterator it = ls.begin(); it != ls.end(); ++it) {int j = *it, t = i*j;if (t > maxn) break;isNotPrime[t] = true;if (i % j == 0) {if ((i / j) % j == 0) g[t] = g[i]*j;else g[t] = g[i/j]*(j-1)*(j-1);break;} else g[t] = g[i]*(j-2);}}for (int i = 2; i <= maxn; i++)g[i] += g[i-1];
}inline void work() {ll rst = 0;for (int i = 1, j; i <= n; i = j + 1) {j = min(n/(n/i), n);rst += (g[j] - g[i-1])*(n/i)*1LL*(n/i);} printf("%lld\n", rst);
}int main() {T = read();init();while (T--) {n = read();work();} return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！