Pollar-Rho算法
Pollar-Rho 算法是一种用于快速分解质因数的算法。 问题引入给定一个正整数$N \in \mathbb{N}_{+}$，试快速找到它的一个因数。 考虑朴素算法，因数是成对分布的，$N$的所有因数可以被分成两块，即$[1,\sqrt N]$和$[\sqrt N+1,N]$。只需要把$[1,\sqrt N]$里的数遍历一遍，再根据除法就可以找出至少两个因数了。这个方法的时间复杂度为$O(\sqrt N)$。
莫比乌斯反演笔记
前置知识正因子求和$\sum_{d|n}$表示对n的所有正因子求和,例如$\sum_{d|8}=1^2+2+2+4^2+8^2 $。 积性函数
莫比乌斯反演
[POI2007]ZAP-Queries gcd与莫比乌斯反演 [HAOI2011]Problem b 上一个题目的更一般的情况，考虑容斥。 P1390 公约数的和 莫比乌斯反演模板，不用分块也可以过。
筛法
相关教程莫比乌斯反演 整除分块 杜教筛
欧几里得算法
这篇是<>，紫书以及<<算法导论>>中欧几里得以及其扩展内容的笔记． 一些基础的数论概念素数与合数首先要有素数和合数
计算因子个数
long long int _num( long long int n){ long long int count = 2; for(long long int i = 2; i <= sqrt(n); i++) { if( n % i == 0 ) { if( i == sqrt(n) && n / i == i ) count++;