首页 > 其他分享 >[bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)

[bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)

时间:2023-02-21 10:06:45浏览次数:40  
标签:4176 return Lucas int sum ret 杜教 mu mod


题面

[bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)_前缀和[bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)_莫比乌斯反演_02的约数个数,给定[bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)_约数个数_03,求 [bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)_前缀和_04

题目分析

有这样一个结论
[bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)_杜教筛_05这道题就是下面这道题的数据增强版,那么这个结论的证明就不再赘述,请自行查看下面的(蒟蒻)博客 ​​传送门:[SDOI2015][bzoj 3994][Luogu P3327] 约数个数和​​

[bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)_#include_06
由于数据范围的增强,我们不能预处理完整个[bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)_前缀和_07,于是就外层整除分块优化

  • 内层杜教筛来算[bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)_约数个数_08的前缀和,时间复杂度为[bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)_约数个数_09
  • 后面平方的底数实际上等于[bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)_前缀和_10约数个数和的前缀和,可以直接[bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)_前缀和_11算,预处理出前[bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)_#include_12约数个数和的前缀和后,总时间复杂度就如杜教筛一样为[bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)_杜教筛_13

总时间复杂度为[bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)_#include_14

AC code
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
typedef long long LL;
const int N = 1e6 + 1;
const int mod = 1e9 + 7;
int Cnt, Prime[N], mu[N], d[N], a[N]; //a[i]存的是i的最小质因数的次数+1
bool IsnotPrime[N];
void init()
{
mu[1] = d[1] = a[1] = 1;
for(int i = 2; i < N; ++i)
{
if(!IsnotPrime[i])
Prime[++Cnt] = i, mu[i] = -1, a[i] = d[i] = 2;
for(int j = 1; j <= Cnt && i * Prime[j] < N; ++j)
{
IsnotPrime[i * Prime[j]] = 1;
if(i % Prime[j] == 0)
{
mu[i * Prime[j]] = 0;
d[i * Prime[j]] = d[i] / a[i] * (a[i * Prime[j]] = a[i] + 1);
break;
}
mu[i * Prime[j]] = -mu[i];
d[i * Prime[j]] = d[i] * (a[i * Prime[j]] = 2);
}
}
for(int i = 1; i < N; ++i)
(d[i] += d[i-1]) %= mod, (mu[i] += mu[i-1]) %= mod;
}

inline int sum_d(int n) //约数个数和的前缀和,也就是后面个平方的底数
{
if(n < N) return d[n];
int ret = 0;
for(int i = 1, j; i <= n; i=j+1)
{
j = n/(n/i);
ret = (ret + (LL)(n/i) * (j-i+1) % mod) % mod;
}
return ret;
}

map<int, int>s;
inline int sum_mu(int n)
{
if(n < N) return mu[n];
if(s.count(n)) return s[n];
int ret = 1;
for(int i = 2, j; i <= n; i=j+1)
{
j = n/(n/i);
ret = (ret - (LL)sum_mu(n/i)*(j-i+1)%mod) % mod;
}
return s[n]=ret;
}

int solve(int n)
{
int ret = 0, last = 0, tmp, tmp2;
for(int i = 1, j; i <= n; i=j+1)
{
j = n/(n/i);
tmp = sum_mu(j), tmp2 = sum_d(n/i), tmp2 = (LL)tmp2 * tmp2 % mod;
//tmp2存后面那个平方的值
ret = (ret + (LL)((tmp-last) % mod) * tmp2 % mod) % mod;
last = tmp;//这利用了一个小优化,本来是sum_mu(j)-sum_mu(i-1),
//我们把sum_mu(i-1)的值存下来,就少计算一次,last存上一次答案
//然而我后来看发现这优化并没有什么卵用,本来就记忆化了...
}
return ret;
}

int main ()
{
init(); int n;
scanf("%d", &n);
printf("%d\n", (solve(n)+mod)%mod);
}

.
.
.
少有的一A

二刷:bzoj rank 7

CODE

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
const int mod = 1e9 + 7;
int prime[MAXN/10], cnt, mu[MAXN], d[MAXN], a[MAXN];
bool vis[MAXN];
inline void Pre_Work(int n) {
mu[1] = d[1] = a[1] = 1;
for(int i = 2; i <= n; ++i) {
if(!vis[i])
prime[++cnt] = i, mu[i] = -1, d[i] = a[i] = 2;
for(int j = 1; j <= cnt && i*prime[j] <= n; ++j) {
vis[i*prime[j]] = 1;
if(i % prime[j] == 0) {
mu[i*prime[j]] = 0;
d[i*prime[j]] = d[i] / a[i] * (a[i*prime[j]] = a[i]+1);
break;
}
mu[i*prime[j]] = -mu[i];
d[i*prime[j]] = d[i] * (a[i*prime[j]] = 2);
}
}
for(int i = 2; i <= n; ++i)
mu[i] += mu[i-1], (d[i] += d[i-1]) %= mod;
}
map<int, int>MU;
inline int sum_mu(int n) {
if(n < MAXN) return mu[n];
if(MU.count(n)) return MU[n];
int re = 1;
for(int i = 2, j; i <= n; i = j+1) {
j = n/(n/i);
re = (re - 1ll * (j-i+1) * sum_mu(n/i) % mod) % mod;
}
return MU[n]=re;
}
map<int, int>D;
inline int sum_d(int n) {
if(n < MAXN) return d[n];
if(D.count(n)) return D[n];
int re = 0;
for(int i = 1, j; i <= n; i = j+1) {
j = n/(n/i);
re = (re + 1ll * (j-i+1) * (n/i) % mod) % mod;
}
return D[n]=re;
}
inline int sqr(int x) { return 1ll*x*x%mod; }
inline int solve(int n) {
int re = 0;
for(int i = 1, j; i <= n; i = j+1) {
j = n/(n/i);
re = (re + 1ll * (sum_mu(j)-sum_mu(i-1)) % mod * sqr(sum_d(n/i)) % mod) % mod;
}
return re;
}
int main() {
int n;
scanf("%d", &n);
Pre_Work(min(n, MAXN-1));
printf("%d\n", (solve(n) + mod) % mod);
}


标签:4176,return,Lucas,int,sum,ret,杜教,mu,mod
From: https://blog.51cto.com/u_15973510/6075818

相关文章

  • [51Nod 1227] 平均最小公倍数 (杜教筛)
    题目描述求题目分析这道题其实是​​[51Nod1238]最小公倍数之和题解​​的简化版,或者说是本质…就直接上公式了令,则此处有一个常识证明如下当时,若,所以与互质的......
  • [51Nod 1237] 最大公约数之和 (杜教筛+莫比乌斯反演)
    题目描述求题目分析乍一看十分像裸莫比乌斯反演,然而的范围让人望而却步于是先变化一下式子枚举令k=Td则此时可以整除分块优化,每次算出相等的上下界后用莫比乌斯反演计......
  • [HDU 5608]Function(莫比乌斯反演 + 杜教筛)
    题目描述有求只有最多组数据题目分析如此一来就可以杜教筛了,然而仅仅这样还是会T,于是我们在想一想如何筛出前面一部分的值令,根据莫比乌斯反演于是用筛出前项就行了......
  • 莫比乌斯反演与杜教筛
    莫比乌斯反演与杜教筛积性函数定义对于一个数论函数\(f\),若满足\(\forall(a,b)=1\)都有\(f(ab)=f(a)f(b)\),那么称\(f\)为积性函数。例子常见的积性函数有很多,......
  • [蓝桥杯 2019 省 A] 组合数问题-Lucas定理、数位dp
    洛谷的题目链接:https://www.luogu.com.cn/problem/P8688Lucas定理,把\(k|binom{i}{j}\)转换成在k进制下存在某个数位i比j小,再转换成反面计算每一位i都比j大,然后就是经典......
  • 基于Lucas-Kanade算法的三维光流提取matlab仿真
    1.算法描述光流的概念:(Opticalfloworopticflow)       它是一种运动模式,这种运动模式指的是一个物体、表面、边缘在一个视角下由一个观察者(比如眼睛、摄像头......
  • Lucas定理证明
    描述:当为大数,为素数时,Lucas定理是用来求的值。适用领域范围:在数论中求大组合数取模。通式:为素数证明:已知为素数,将非负整数转化成进制数:由于p是素数对于,都有由二项式定......
  • lucas定理学习笔记
    lucas学习笔记小蒟蒻的第一篇学术文章,对lucas理解不够透彻,如有错误,望指正,同时望支持注:下文定义\(\binom{a}{b}\)为\(\frac{b!}{a!(b-a)!}\quad\)(即组合数)定理内容:......
  • Lucas 定理
    简述当问题规模很大,而模数是一个不大的质数的时候,就不能简单地通过递推求解来得到答案,需要用到Lucas定理。LucasLucas定理内容如下:对于质数\(p\),有\[\binom{n}{m}......
  • 杜教筛
    杜教筛设现在要求积性函数\(f\)的前缀和,设\(\sum_{i=1}^{n}f(i)=S(n)\)找一个积性函数\(g\),考虑它们的狄利克雷卷积的前缀和\[\sum_{i=1}^{n}(f*g)(i)=\sum_{i=1}^......