BZOJ4916: 神犇和蒟蒻(杜教筛)
2018-07-20 05:47:50来源:博客园 阅读 ()
题意
求
$$\sum_{i = 1}^n \mu(i^2)$$
$$\sum_{i = 1}^n \phi(i^2)$$
$n \leqslant 10^9$
Sol
zz的我看第一问看了10min。
感觉自己智商被侮辱了qwq
基础太垃圾qwq。
算了正经点吧,第一问答案肯定是$1$,还不明白的重学反演吧。
第二位其实也不难
定理:
$\phi(i^2) = i\phi(i)$
$\sum_{d | n} \phi(d) = n$
显然$i$
考虑杜教筛的套路式子
$$g(1)s(n) = \sum_{i = 1}^n g(i)s(\frac{n}{i}) - \sum_{i = 2}^n g(i)s(\frac{n}{i})$$
当我们选择$g(i) = id(i) = i$时卷积的前缀和是比较好算的
$(g * s)(i) = \sum_{i = 1}^n i^2 = \frac{n * (n + 1) * (2n + 1)}{6}$
然后上杜教筛就行了
$$s(n) = \frac{n * (n + 1) * (2n + 1)}{6} - \sum_{i = 2}^n i \phi(\frac{n}{i})$$
人傻自带大常数
#include<cstdio> #include<map> #define LL long long using namespace std; const int MAXN = 1e7 + 10, mod = 1e9 + 7; const LL inv = 166666668; int N, prime[MAXN], vis[MAXN], tot; LL phi[MAXN]; map<int, LL> ans; void GetPhi(int N) { vis[1] = phi[1] = 1; for(int i = 2; i <= N; i++) { if(!vis[i]) prime[++tot] = i, phi[i] = i - 1; for(int j = 1; j <= tot && i * prime[j] <= N; j++) { vis[i * prime[j]] = 1; if(!(i % prime[j])) {phi[i * prime[j]] = phi[i] * prime[j]; break;} phi[i * prime[j]] = phi[i] * phi[prime[j]]; } } for(int i = 1; i <= N; i++) phi[i] = (1ll * i * phi[i] % mod + phi[i - 1] % mod) % mod; } LL Query(LL x) { return (x * (x + 1) / 2) % mod; } LL S(LL N) { if(ans[N]) return ans[N]; if(N <= 1e7) return phi[N]; LL sum = N * (N + 1) % mod * (2 * N + 1) % mod * inv % mod, last = 0; for(int i = 2; i <= N; i = last + 1) { last = N / (N / i); sum -= S(N / i) % mod * (Query(last) - Query(i - 1)) % mod; sum = (sum + mod) % mod; } return ans[N] = (sum % mod + mod) % mod; } int main() { GetPhi(1e7); scanf("%d", &N); printf("1\n%lld", S(N)); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 图论初步<蒟蒻专属文章> 2020-02-08
- P1880 [NOI1995]石子合并 2019-05-04
- 树状结构之主席树 2019-01-03
- NOIP游记 Day0 2018-11-12
- 极简版线段树 2018-09-18
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