BZOJ4804: 欧拉心算(莫比乌斯反演 线性筛)
2018-07-20 05:47:47来源:博客园 阅读 ()
题意
求$$\sum_1^n \sum_1^n \phi(gcd(i, j))$$
$T \leqslant 5000, N \leqslant 10^7$
Sol
延用BZOJ4407的做法
化到最后可以得到
$$\sum_{T = 1}^n \frac{n}{T} \frac{n}{T} \sum_{d \mid T}^n \phi(d) \mu(\frac{T}{d})$$
后面的那个是积性函数,直接筛出来
注意这个函数比较特殊,筛的时候需要分几种情况讨论
1. $H(p) = p - 2$
2. $H(p^2) = p^2 - 2p + 1$
3. $H(p^{k + 1}) = H(p^k) * p$
// luogu-judger-enable-o2 #include<cstdio> #include<algorithm> #define LL long long using namespace std; const int MAXN = 1e7 + 10, mod = 1e9 + 7; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int prime[MAXN], vis[MAXN], tot; LL H[MAXN], low[MAXN]; void GetH(int N) { H[1] = vis[1] = 1; for(int i = 2; i <= N; i++) { if(!vis[i]) prime[++tot] = i, H[i] = i - 2, low[i] = i; for(int j = 1; j <= tot && i * prime[j] <= N; j++) { vis[i * prime[j]] = 1; if(!(i % prime[j])) { low[i * prime[j]] = low[i] * prime[j]; if(low[i] == i) { if(low[i] == prime[j]) H[i * prime[j]] = (H[i] * prime[j] + 1); else H[i * prime[j]] = H[i] * prime[j]; } else H[i * prime[j]] = H[i / low[i]] * H[low[i] * prime[j]]; break; } H[i * prime[j]] = H[i] * H[prime[j]]; low[i * prime[j]] = prime[j]; } } for(int i = 2; i <= N; i++) H[i] = H[i - 1] + H[i]; } int main() { GetH(1e7 + 5); int T = read(); while(T--) { int N = read(), last; LL ans = 0; for(int i = 1; i <= N; i = last + 1) { last = N / (N / i); ans = ans + 1ll * (N / i) * (N / i) * (H[last] - H[i - 1]); } printf("%lld\n", ans); } return 0; } /* 3 7001 123000 10000000 */
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++贪心算法实现活动安排问题 2019-11-04
- 「中山纪中集训省选组D2T1」书堆 欧拉常数 2019-08-16
- JZOJ.1153【贪心算法】硬币交换 2019-08-16
- 欧拉函数 2018-10-03
- BZOJ3288: Mato矩阵(欧拉函数 高斯消元) 2018-07-19
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash