目录
质数与约数
1. 算法分析
1.1 基本概念
质数: 作为最小单位，无法在进行拆分
约数: 8的约数有1，2，4，8
1.2 常用公式和性质
1.2.1 质数
重要结论
- int范围内最多只有10个不重复质因子，且所有质数的次数总和不能超过30
- 素数的大小:x/lnx,素数的个数:xlnx
- 任何一个合数n一定存在一个<=sqrt(n)的质因子
1.2.2 约数
常用公式
- n的约数个数: 对于一个大于1正整数可以分解质因数：n=(p1 ^ a1) * (p2 ^ a2) * ... *(pk ^ ak),则n的正约数个数为:f(n) = (a1+1)(a2+1)...(ak+1)
- n的约数和：对于一个大于1正整数n可以分解质因数：n=(p1 ^ a1) * (p2 ^ a2) * ... *(pk ^ ak),那么n的(a₁+1)(a₂+1)(a₃+1)…(ak+1)个正约数的和为：f(n)=(p1 ^ 0 + p1 ^ 1 + p1 ^ 2 + … + p1 ^ a1)(p2 ^ 0 + p2 ^ 1 + p2 ^ 2+ … + p2 ^ a2)…(pk ^ 0 + pk ^ 1 + pk ^ 2 +…+ pk ^ ak），其中：计算每个(pi ^ 0 + pi ^ 1 + pi ^ 2 + … + pi ^ ai)时可以借助秦九韶公式优化运算
- 1~N中所有数的约数个数和
N/1+N/2+...+N/N = N(lnN + C) ,C= 0.57721566490153286060651209 - 1~N中所有数的约数和:
1 * N / 1 + 2 * N / 2 + ... + N * N / N
重要结论
- int范围内拥有最多约数的那个数字拥有1600个约数
- 1~N中任何数的不同质因子不会超过10个，且所有质因子的指数总和不超过30
2. 板子
2.1 质数
2.1.1 素数判定
- 试除法判定素数(小素数)
// 判断是否为素数
bool is_prime(int x)
{
if (x < 2) return false; // 1不是素数
for (int i = 2; i <= x / i; ++i) // 从2循环到sqrt(x),但是循环进行条件不写i <= sqet(x),因为太慢；不写i * i <= x，因为可能有溢出的风险
if (x % i == 0) return false;
return true;
}
- miller-rabin判断素数(大素数)
#include <bits/stdc++.h>
using namespace std ;
typedef unsigned long long ll;
ll multi(ll a, ll b, ll mod) {
ll ret = 0;
while(b) {
if(b & 1) ret = ret + a;
if(ret >= mod) ret -= mod;
a = a + a;
if(a >= mod) a -= mod;
b >>= 1;
}
return ret;
}
ll quick_pow(ll a, ll b, ll mod) {
ll ret = 1;
while(b) {
if(b & 1) ret = multi(ret, a, mod);
a = multi(a, a, mod);
b >>= 1;
}
return ret;
}
bool Miller_Rabin(ll n) {
ll u = n - 1, pre, x;
int i, j, k = 0;
if(n == 2 || n == 3 || n == 5 || n == 7 || n == 11) return true;
if(n == 1 || (!(n % 2)) || (!(n % 3)) || (!(n % 5)) || (!(n % 7)) || (!(n % 11)))
return false;
for(; !(u & 1); k++, u >>= 1);
srand(time(NULL));
for(i = 0; i < 5; i++) {
x = rand() % (n - 2) + 2;
x = quick_pow(x, u, n);
pre = x;
for(j = 0; j < k; j++) {
x = multi(x, x, n);
if(x == 1 && pre != 1 && pre != (n - 1))
return false;
pre = x;
}
if(x != 1) return false;
}
return true;
}
2.1.2 质因数分解
- 试除法分解质因数(小整数) : O(sqrt(x))
int x;
cin >> x;
for (int i = 2; i <= x / i; ++i) // 因为一个数x的所有因子内只会有一个大于sqrt(x), 所以只要枚举到sqrt(x),而后单独判断大于sqrt(x)的那个即可
{
if (x % i == 0) // 如果能够整除
{
int s = 0; // 记录能够整除几次
while (x % i == 0)
{
s++;
x /= i;
}
printf("%d %d
", i, s); // 输出因子和次数
}
}
if (x > 1) printf("%d %d
", x, 1); // 如果有剩下的数字必然比sqrt(x)大，因为如果比sqrt(x)小，那么在做上一步的枚举时就已经被除掉了，一旦有，就必然次数为1
- 更快的质因数分解:先筛素数，然后拿素数判断是不是质因数 O(sqrt(x/lnx))
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int main() {
...
for (int i = 0; prime[i] <= t / prime[i]; ++i)
{
int p = prime[i];
if (t % p == 0)
{
int s = 0;
while (t % p == 0)
{
s++;
t /= p;
}
factor[fcnt++] = {p, s};
}
}
if (t > 1) factor[fcnt++] = {t, 1};
...
}
- pollard_rho分解质因数(大整数)
typedef long long LL;
const int maxn = 10000;
const int S = 20;
LL factor[maxn];
int tot; // 记录有几个质因子
//返回(a * b) % c,a,b,c<2^63
LL multi_mod(LL a, LL b, LL c)
{
a %= c;
b %= c;
LL ret = 0;
while(b)
{
if (b & 1)
{
ret += a;
if (ret >= c) ret -= c;
}
a <<= 1;
if(a >= c) a -= c;
b >>= 1;
}
return ret;
}
//返回x^n mod c ,非递归版
LL pow_mod(LL x, LL n, LL mod)
{
LL ret = 1;
while(n)
{
if(n & 1) ret = multi_mod(ret, x, mod);
x = multi_mod(x, x, mod);
n >>= 1;
}
return ret;
}
//以a为基，n-1=x*2^t，检验n是不是合数
bool check(LL a, LL n, LL x, LL t)
{
LL ret = pow_mod(a, x, n), last = ret;
for (int i = 1; i <= t; i++)
{
ret = multi_mod(ret, ret, n);
if (ret == 1 && last != 1 && last != (n-1)) return 1;
last = ret;
}
if (ret != 1) return 1;
return 0;
}
/*素数测试*/
bool Miller_Rabin(LL n)
{
LL x = n - 1, t = 0;
while ((x & 1) == 0) x >>= 1, t++;
bool flag = 1;
if (t >= 1 && (x & 1) == 1)
{
for(int k = 0; k < S; k++)
{
LL a = rand()%(n-1) + 1;
if (check(a, n, x, t))
{
flag = 1; break;
}
flag = 0;
}
}
if (!flag || n == 2) return 0;
return 1;
}
LL gcd(LL a,LL b)
{
if (a == 0) return 1;
if (a < 0) return gcd(-a, b);
while (b)
{
LL t = a % b;
a = b;
b = t;
}
return a;
}
/*大整数素因子分解*/
LL Pollard_rho(LL x, LL c)
{
LL i = 1, x0 = rand() % x, y = x0, k = 2;
while(1)
{
i++;
x0 = (multi_mod(x0, x0, x) + c) % x;
LL d = gcd(y - x0, x);
if (d != 1 && d != x)
{
return d;
}
if (y == x0) return x;
if (i == k)
{
y = x0;
k += k;
}
}
}
//递归进行质因数分解N
// 输入n为要质因数分解的大整数，质因数分解完后tot为质因数个数，factor存储分解后得到的质因数
// 使用pollard_rho随机算法
void findfac(LL n)
{
if (!Miller_Rabin(n))
{
factor[tot++] = n;
return;
}
LL p = n;
while(p >= n) p = Pollard_rho(p, rand() % (n-1) + 1);
findfac(p);
findfac(n / p);
return ;
}
- 阶乘分解
/*
把阶乘n!分解的算法：
1.求出n的所有质因数（欧拉筛法）
2.计算每个质因数的次数
原理：
1.所有的质因子有哪些？
对于n来说，如果n=(p1^a1)*(p2^a2)*...*(pn^an)
那么1~n-1最大的质数个数也只有n个
所有对n做个筛质因数就能得到n!的所有质因子pi
2.质因子的次数？
从每个质因子的角度考虑，如果某个t属于[1,n],一旦p1|t,那么将对a1贡献1；
如果(p1)^2|t,那么将对a1贡献2；所有只需要把n/p1+n/(p1**2)+...+n/n加起来即可
*/
#include <bits/stdc++.h>
using namespace std;
int const N = 1e6 + 10;
int prime[N], cnt;
int st[N];
// 筛素数
void init(int n)
{
for (int i = 2; i <= n; ++i)
{
if (!st[i]) prime[cnt++] = i;
for (int j = 0; prime[j] <= n / i; ++j)
{
st[prime[j] * i] = 1;
if (i % prime[j] == 0) break;
}
}
}
int main()
{
int n;
cin >> n;
init(n);
for (int i = 0; i < cnt; ++i)
{
int p = prime[i]; // 每个质数
int s = 0; // 计算次数
for (int j = n; j; j /= p) s += j / p;
printf("%d %d
", p, s);
}
return 0;
}
2.1.3 筛素数
- 埃氏筛法
// 埃氏筛法
void get_prime(int n)
{
for (int i = 2; i <= n; ++i) // 枚举从2~n的所有数
{
if (!st[i]) // 如果这个数字没有被筛过(这个数字必为素数)
{
prime[cnt++] = i; // 记录这个素数
for (int j = i + i; j <= n; j += i) st[j] = 1; // 把素数的所有倍数都筛掉
}
}
}
- 线性筛(欧拉筛)
// 线性筛素数（以下把prime[j]这个数简写为pj）
// 如何保证线性:一个合数只能被筛掉一次
// 如何保证一个数字只被筛掉一次:这个数字只被它的最小质因数筛掉，当它的其他质因数想要筛掉它时，将无法进行筛除操作
// 可以证明：pj是pj*i的最小质因数：
// ①假设i % pj == 0, 因为pj从小到大枚举，所以pj是i的最小质因数，所以pj是pj*i的最小质因数
// ②假设i % pj != 0, 则pj比i的最小质因数还要小，则pj是pi*i的最小质因数
// 综上，无论是哪种情况，pj都是pj*i的最小质因数
// 假设pj*i会被多次筛掉，那么将多次执行st[prime[j] * i] = true;语句，而从第二次执行该语句后，i比之前大，
// 那么pj比之前的小，然而之前的pj已经是最小质因数，矛盾，假设不成立
void get_prime(int n)
{
for (int i = 2; i <= n; ++i)
{
if (!st[i]) prime[cnt++] = i; // 如果这个数字没有被记录，那么这个数字必然为素数，记录一下
// pj枚举到n/i是因为:pj小于等于n/i才能保证pj*i小于等于n
for (int j = 0; prime[j] <= n/i; ++j)
{
st[prime[j] * i] = true; // 筛掉pj*i这个合数
if (i % prime[j] == 0) break;
}
}
}
2.2 约数
2.2.1 求x相关
- 求x的约数(O(sqrt(x)))
// 试除法求约数
vector<int> get_divisors(int x)
{
vector<int> res; // 记录答案
for (int i = 1; i <= x /i; ++i) // 枚举到sqrtx(x)
{
if (x % i == 0) // 如果能够整除
{
res.push_back(i); // 放入i
if (i != x / i) res.push_back(x / i); // x/i不等于i，也放入答案中
}
}
sort(res.begin(), res.end()); // 排序
return res;
}
- 求x的约数个数(O(sqrt(x)))
map<int, int> prime; // 记录质数，使用map是因为如果使用数组一会遍历时会把不是质数的也遍历进去
while (n--) // 读入n个数
{
int a;
scanf("%d", &a);
for (int i = 2; i <= a / i; ++i) // 对每一个求质因数
{
while (a % i == 0)
{
prime[i]++; // 记录每个质数出现次数
a /= i;
}
}
if (a > 1) prime[a] ++; // 记录大于sqrt(a)的那个质数的次数
}
unsigned long long res = 1;
for (auto p: prime) res = res * (p.second + 1) % mod; // 约数个数定理
- 求x的约数和(O(sqrt(x)))
// 计算出每个质数的次数
while(n--)
{
int a;
scanf("%d", &a);
for (int i = 2; i <= a / i; ++i)
{
while (a % i == 0)
{
primes[i] ++;
a /= i;
}
}
if (a > 1) primes[a] ++;
}
PLL res = 1;
// 使用约数和定理，这里借助秦九韶公式计算
for (auto pi: primes)
{
int p = pi.first, a = pi.second; // p为质因数，a为质因数出现的次数
PLL t = 1;
while(a--) t = (p * t + 1) % mod ;
res = res * t % mod;
}
2.2.2 求1~N相关
- 求1~N中所有数的约数(O(nlnn))
vector<int> factor[500010];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n / i; ++j)
factor[i * j].push_back(i);
for (int i = 1; i <= n; ++i)
for (int j = 0; j < factor[i].size(); ++j)
printf("%d ", factor[i][j]);
- 求1~N中所有数的约数个数和(O(n))
sum = 0;
for(i=1;i<=n;i++)
sum += n / i;
printf("n = %lld
",n);
printf("%lld
",sum);
- 求1~N中所有数的约数和(O(n))
sum = 0;
for(i=1;i<=n;i++)
sum += i * (n / i);
printf("n = %lld
",n);
printf("%lld
",sum);
2.1.3 gcd
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b): a;
}
3. 例题
acwing1291轻拍牛头
共有 N 个整数 A1,A2,…,AN，对于每一个数 Ai，求其他的数中有多少个是它的约数。
// i 是所有i的倍数的约数
#include <bits/stdc++.h>
using namespace std;
int const N = 1e6 + 10;
int a[N], cnt[N], n, res[N];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
cnt[a[i]] ++;
}
for (int i = 1; i <= N; ++i) {
if (!cnt[i]) continue;
for (int j = 1; j * i <= N; ++j) {
if (!cnt[j * i]) continue;
res[j * i] += cnt[i];
}
}
for (int i = 1; i <= n; ++i) cout << res[a[i]] - 1 << endl;
return 0;
}
acwing1294樱花
/* 从题意可以知道x和y都大于n!
设y=n!+k(k∈N∗)
1/x+1/(n!+k)=1/n!
化简得:x=(n!)**2 / k + k
则x的个数就是(n!)**2的约束个
然后 约数个数和+阶乘分解 处理 */
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int const N = 1e6 + 10, MOD = 1e9 + 7;
int prime[N], cnt;
int st[N];
// 筛素数
void init(int n)
{
for (int i = 2; i <= n; ++i)
{
if (!st[i]) prime[cnt++] = i;
for (int j = 0; prime[j] <= n / i; ++j)
{
st[prime[j] * i] = 1;
if (i % prime[j] == 0) break;
}
}
}
int main()
{
int n;
cin >> n;
init(N);
int res = 1;
for (int i = 0; i < cnt; ++i)
{
int p = prime[i]; // 每个质数
int s = 0; // 计算次数
for (int j = n; j; j /= p) s += j / p;
res = res * (LL)(s * 2 + 1) % MOD;
}
cout << res;
return 0;
}
acwing198反素数
对于任何正整数x，其约数的个数记作g(x)，例如g(1)=1、g(6)=4。
如果某个正整数x满足：对于任意的小于x的正整数 i，都有g(x)>g(i) ，则称x为反素数。
例如，整数1，2，4，6等都是反素数。
现在给定一个数N，请求出不超过N的最大的反素数。
N~1e9
// 推导可知:反素数必须满足
// 1. 不同质因子数目最多9个
// 2. 所有质因子次数总和小于等于31
// 3. 质因子次数单调不增
// 从以上几个条件可以看出，dfs的空间其实很小
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
int ans, maxv, n, pirme[] = {2, 3, 5, 7, 11, 13, 17, 19, 23}; // 最多指数只能有9个
// u当前的质数下标，last上一次的最大次数，sum_all总和，sum_fac约数个数和， sum_c次数和
void dfs(int u, int last, int sum_all, int sum_fac, int sum_c) {
if (sum_fac > maxv || (sum_fac == maxv && sum_all < ans)) { // 如果当前约数个数和最多或者当前总和更小
maxv = sum_fac;
ans = sum_all;
}
if (u >= 9 || sum_c >= 31) return;
int fact = 1;
for (int i = 0; i <= last; ++i) { // 每个质数取i次
if ((LL)sum_all * fact > n) continue; // 如果乘完大于n
if (sum_c + i >= 31) continue;
dfs(u + 1, i, sum_all * fact, sum_fac * (i + 1), sum_c + i);
fact *= pirme[u];
}
}
int main () {
cin >> n;
dfs(0, 30, 1, 1, 0);
cout << ans;
return 0;
}
acwing200 Hankson的趣味题
n组测试样例，每组测试样例输入:a0, a1, b0, b1
求出有多少个x满足，(x, a0)=a1, [x, b0]=b1
n~2000, a0、a1、b0、b1~2e9
/*
本题需要找出x使得(x, a0)=a1, [x, b0] = b1
从上面的关系可以看出：x是b1的因子，因此我们考虑枚举b1的所有因子
现在如何快速获取b1的所有因子呢？
可以先对b1做质因子分解，然后dfs暴搜每个质因子的次数即可
分析以下这样做的时间复杂度:
质因子分解的复杂度为: sqrt(x/lnx)
dfs一共只有1536种情况，可以看出搜索空间非常小
*/
#include<bits/stdc++.h>
using namespace std;
int n;
int const N = 5e5 + 10;
int prime[N], cnt, st[N];
struct Fac
{
int p, s;
}factor[1600];
int fcnt;
int a0, a1, b0, b1;
int divisor[N], dcnt;
// 欧拉筛法
void init(int n)
{
for (int i = 2; i <= n; ++i)
{
prime[cnt++] = i;
for (int j = 0; prime[j] <= n / i; ++j)
{
st[prime[j] * i] = 1;
if (i % prime[j] == 0) break;
}
}
}
//暴搜每个质因子的次数得到b1的因子
void dfs(int u, int p)
{
if (u == fcnt)
{
divisor[dcnt++] = p;
return;
}
for (int i = 0; i <= factor[u].s; ++i)
{
dfs(u + 1, p);
p *= factor[u].p;
}
}
int main()
{
init(N - 1);
cin >> n;
while (n--)
{
dcnt = fcnt = 0;
cin >> a0 >> a1 >> b0 >> b1;
// 把b1做质因子分解
int t = b1;
for (int i = 0; prime[i] <= t / prime[i]; ++i)
{
int p = prime[i];
if (t % p == 0)
{
int s = 0;
while (t % p == 0)
{
s++;
t /= p;
}
factor[fcnt++] = {p, s};
}
}
if (t > 1) factor[fcnt++] = {t, 1};
// dfs暴搜出b1的因子
dfs(0, 1);
// 统计出答案个数
int res = 0;
for (int i = 0; i < dcnt; ++i)
{
int x = divisor[i];
if (__gcd(a0, x) == a1 && (long long)x * b0 / __gcd(x, b0) == b1) res++;
}
cout << res << endl;
}
return 0;
}