首页 > 其他分享 >2024-2-18 数论学习笔记

2024-2-18 数论学习笔记

时间:2024-02-18 22:25:31浏览次数:24  
标签:lfloor frac 数论 18 sum rfloor 2024 ln int

zak 讲数论专题,好难,听不懂,整理一下。
借鉴了 zak 的课件。
还没写完呐,还会更新的。

目录

一、线性筛

筛出 \(n\) 以内的所有质数。
\(n ≤ 10^8\)。

直接埃氏筛是 \(O(n \ln \ln n)\) 的,但是一个合数会被筛多次,所以需要优化。线性筛时考虑一个合数只被它的最小因数 \(p\) 筛,设合数为 \(xp\),先枚举 \(x\),再枚举 \(p\),如果 \(x \bmod p = 0\),那么 \(xp\) 就不是最小因数,就跳出循环,每个合数只会被筛一次,时间复杂度 \(O(n)\)。

const int N = 1e8 + 5;
int n, ip[N], p[N], cnt;
void init() {
	ip[1] = 1;
	FOR(i, 2, n) {
		if(!ip[i]) {
			p[++cnt] = i;
		}
		for(int j = 1; j <= cnt && i * p[j] <= n; j++) {
			ip[i * p[j]] = 1;
			if(i % p[j] == 0) break;
		}
	}
}

二、Dirichlet 前缀和

给定数组 \(a\),求数组 \(b\) 满足 \(b_{x} = \sum_{y|x}a_y\)。
\(n \le 2\times 10^7\)。

直接做是 \(O(n \ln n)\) 的,无法通过,考虑优化。这个式子可以进行转化,把 \(A\) 和 \(B\) 看作数组 \(a\) 和 \(b\) 的数论函数,那么通过 Dirichlet 卷积得出 \(A*I=B\),把题面转化为求 \(A\) 与 \(I\) Dirichlet 卷积的前 \(n\) 位。然后考虑如何计算,先将积性函数 \(I\) 拆分成一堆积性函数,设 \(p_i\) 为第 \(i\) 大的素数,定义 \(f_i(p^k)=[p=p_i]\),那么 \(I = \prod f_i\),所以题目又转化为 \(B=A*\prod f_i\),这可以直接埃氏筛计算,时间复杂度 \(O(n \ln \ln n)\)。

const int N = 2e7 + 5;
int n;
uint a[N]; int p[N];
void solve() {
	cin >> n >> seed;
	FOR(i, 1, n) a[i] = rnd();
	uint ans = 0;
	p[1] = 1;
	FOR(i, 1, n) {
		if(!p[i]) {
			for(int j = 1; i * j <= n; j++) {
				a[i * j] += a[j];
				p[i * j] = 1;
			}
		}
		ans ^= a[i];
	}
	cout << ans << endl;
}

三、整除分块

求 \(\sum_{i=1}^{n}d(i)\)。
\(n \le 10^{12}\)。

先推导式子 \(\sum_{i=1}^{n}d(i)=\sum_{i=1}^{n}\sum_{xy=i}1=\sum_{xy\le n}1=\sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor\)。而 \(\lfloor \frac{n}{i} \rfloor\) 只有 \(O(\sqrt{n})\) 种取值,且每种取值连续,考虑一起计算,对于一个左端点 \(l\) 找出连续值的最右端点 \(r\),就是 \(\lfloor \frac{n}{r} \rfloor \ge \lfloor \frac{n}{l} \rfloor\) 的最大的 \(r\),也就是 \(\left \lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \right \rfloor\),时间复杂度 \(O(\sqrt{n})\)。

ll n, ans;
void solve() {
	cin >> n;
	for(ll l = 1, r; l <= n; l = r + 1) {
		r = n / (n / l);
		ans += (r - l + 1) * (n / l);
	}
	cout << ans << endl;
}

四、莫比乌斯函数

例一

给定序列 \(A, B, C\),求 \(\sum_{i=1}^{n}\sum_{j=1}^{n} A(i)B(j)C(\gcd(i, j))\)。
\(n \le 10^6\)。

先枚举 \(\gcd\)。

\[\sum_{i=1}^{n}\sum_{j=1}^{n} A(i)B(j)C(\gcd(i, j)) \]

\[=\sum_{g=1}^{n}C(g) \sum_{i=1}^{\lfloor\frac{n}{g}\rfloor} \sum_{j=1}^{\lfloor\frac{n}{g}\rfloor} A(ig)B(jg)[\gcd(i,j)=1]\]

然后替换 \(\gcd\) 为 \(\mu\) 函数然后提出来。

\[=\sum_{g=1}^{n}C(g) \sum_{i=1}^{\lfloor\frac{n}{g}\rfloor} \sum_{j=1}^{\lfloor\frac{n}{g}\rfloor} A(ig)B(jg) \sum_{t|i,t|j}\mu(t)\]

\[=\sum_{g=1}^{n} \sum_{t=1}^{\lfloor\frac{n}{g}\rfloor} C(g)\mu(t) (\sum_{i=1}^{\lfloor\frac{n}{gt}\rfloor}A(igt)) (\sum_{j=1}^{\lfloor\frac{n}{gt}\rfloor} B(jgt))\]

把 \(C\) 和 \(\mu\) 卷起来,设 \(D(x)=\sum_{d|x}C(x)\mu(\frac{x}{d})\)。

\[=\sum_{k=1}^{n} D(k) (\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}A(ik)) (\sum_{j=1}^{\lfloor\frac{n}{k}\rfloor} B(jk))\]

可以 \(O(n \ln n)\) 或者 \(O(n \ln \ln n)\) 实现。

标签:lfloor,frac,数论,18,sum,rfloor,2024,ln,int
From: https://www.cnblogs.com/kevinlikescoding/p/18018779

相关文章

  • .NET周刊【2月第1期 2024-02-04】
    祝大家新年快乐,龙年大吉~国内文章C#/.NET/.NETCore优秀项目和框架2024年1月简报https://www.cnblogs.com/Can-daydayup/p/18000401本文介绍了公众号“追逐时光者”定期分享的C#/.NET/.NETCore优秀项目和框架,包括项目介绍、功能特点、使用方式和功能截图,并提供了源码地址。文......
  • 2024-02-18-物联网C语言(7-字符串处理函数)
    7.字符串7.1获取字符串的长度函数-strlen头文件:#include<string.h>函数定义:size_tstrlen(constchar*s)参数:s-指定的字符串返回值:当前字符串的长度#include<stdio.h>#include<string.h>intmain(intargc,charconst*argv[]){//使用strlen获取字符......
  • 2024.2.18 近期练习
    P4764值域为\([l,r]\)的生成森林,也就是把值\(\gel\)的边拿出来生成森林,其中边\(\ler\)的权值和。我们现在要求所有\(l\),$\gel$边的生成森林中边有哪些。考虑从大往小加边,设当前加入第条边\((u,v,w)\)。因为这条边最小,所以这条边必选。若\(u,v\)不连通,那么直接......
  • 闲话2.18
    晚上开始模拟费用流了......
  • winter 2024 第三四周周报
    内容week3day1https://www.cnblogs.com/bible-/p/18018423这天是打寒假牛客2,请假了后面补的题,补了10道吧,感觉这些题花点时间都是可以写的,但是赛时真的很容易被卡,板子题也挺多,线段树、树状数组、字典树(太久不写有点忘了)week3day3https://www.cnblogs.com/bible-/p/18011488打......
  • [2024 AtCoder 比赛历程]
    2024.1.20ABC337-G题目大意:给定一棵树,对于树上的每个点$u$,定义$f[u]$表示满足点$w$在点$u$到点$v$的路径中,且$w>v$的点对$(w,v)$的数量。$u$可以等于$w$。解法:比赛时先考虑将一个点钦定为$w$时,该点对其他点的贡献。发现对于一个点,它可以通过它的一个子树内......
  • (2024.2.5-2024.2.18)C语言学习小结
    这两周主要围绕《HeadfirstC》这本书展开C语言学习,同时尝试学习DES密码算法C程序。基本内容《HeadfirstC》学习的内容基本上就是进程与通信、网络、线程这块。以下是思维导图:实践练习除了书上的一些小练习之外,我也实践写了HFC的C语言实验室2的程序,一波三折,详见C代码......
  • 2024-02-18-物联网C语言(6-动态内存申请)
    6.动态内存申请6.1动态分配概述​ 在数组一章中,介绍过数组的长度是预先定义好的,在整个程序中固定不变,但是在实际的编程中,往往会发生这种情况,即所需的内存空间取决于实际输入的数据,而无法预先确定。​ 为了解决上述问题,C语言提供了-些内存管理函数,这些内存管理函数可以按需......
  • 2024牛客寒假算法基础集训营2
    C.TokitsukazeandMin-MaxXOR题解:01Trie观察后发现对序列\(a\)排序并不影响结果然后容易知道,对于\(i<j,a_i\oplusa_j\leqk\),一共有\(2^{i-j-1}\)种序列\(b\)满足条件,特别的,如果\(i=j\),只有\(1\)种满足条件那么现在问题就转换为,我们固定\(a_......
  • 亚马逊云ec2-user安装node-js-18.16.0
    1,下载vnm管理工具curl-o-https://raw.githubusercontent.com/nvm-sh/nvm/v0.39.1/install.sh|bashexportNVM_DIR="$HOME/.nvm"[-s"$NVM_DIR/nvm.sh"]&&\."$NVM_DIR/nvm.sh"#Thisloadsnvm[-s"$NVM_DIR/bash......