整除基本知识
性质
- 若\(a|b\) 且 \(b|c\)，则 \(a|c\)。
- 若\(a|b\) 且 \(b|c\)，则 对于任意的整数 \(x、y\)，有 \(a|(bx +cy)\)
- 对于整数 \(m\neq 0\)，\(a|b \leftrightarrow b|a\)
寻找约数
暴力
for (int i = 1; i <= n; i++)
{
if (x % i == 0) ans[++cnt] = i;
}
优化
约数肯定是成对出现的。
对于 \(120\)。
如 \(2,60\)
即如果 \(k\) 是 \(n\) 的约数，那么 \(\frac nk\) 也一定是 \(n\) 的约数。
不妨设 \(k\) 是较小的一个（为了优化枚举时间），那么显然。
\[k \leq \frac n k \]\[k \leq \sqrt n \]那么对 \(k\) 枚举，时间复杂度就降低到了 \(\operatorname O(\sqrt n)\)。
int find_divisors(int n, int a[])
{
int cnt = 0;
for (int k = 1; k * k <= n; k++)
{
if (n % k == 0)
{
a[++cnt] = k;
if (k != n / k) a[++cnt] = n / k;
}
}
return cnt;
}
数列中的倍数数
P2926 USACO08DEC Patting Heads S
从枚举倍数的角度思考：对于一个数 $ i $ 若它在原数组中出现了 $ c[i] $ 次，那么 $ i $ 这个数会对它的每一个倍数产生 $ c[i] $ 的贡献。这样就可以通过查询这样产生的贡献的总和来计算答案了，其时间复杂度为：
\[O(nlogn) \]代码：
#include <bits/stdc++.h>
using namespace std;
const int Maxn=1000100;//数组大小
const int Bignumber=1000000;
int n,a[Maxn],c[Maxn],w[Maxn];//n个数，数列，数字统计容器，贡献值
int main() {
scanf("%d",&n);//输入
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);//输入数列
c[a[i]]++;
}
for(int i=1;i<=Bignumber;i++)
for(int j=i;j<=Bignumber;j+=i)
w[j]+=c[i];//i这个数会对j产生c[i]的贡献
for(int i=1;i<=n;i++)
printf("%d\n",w[a[i]]-1);//输出时要把a[i]对自己的贡献减去
return 0;
}
快速求因子数
依靠两个结论
- 一个正整数一定能分解为若干质数\(\space n\space\)次方的乘积。
- 一个数的因子数等于该数分解为若干质数\(\space n\space\)次方的乘积后每个质数的次方数加一的乘积。
举个例子
\[120=2^3\times3\times5 \]那么因子数则是\(\space (3+1)\times(1+1)\times(1+1)=16\)。
代码实现
ll getInShu(ll n)
{
ll ans = 1;
for (int i = 2; i * i <= n; i++)
{
if (n % i == 0)//质因数分解
{
ll cnt = 0;//即这个因数的次方
while(n % i == 0)
{
++cnt;
n /= i;
}
ans = (ans mod) * ((cnt + 1) mod);
ans = ans mod;
}
}
if (n != 1)//说明剩下最后一个质因数
{
ans *= 2;
}
return ans mod;
}