约数个数定理可以计算出一个数约数的个数
约数个数定理
对于一个大于1正整数n可以分解质因数：
则n的正约数的个数就是
其中
定理简证
首先同上，n可以分解质因数
由约数定义可知
故根据乘法原理：n的约数的个数就是
例
例：正整数378000共有多少个正约数？
解：将378000分解质因数
实现
int f1(int n) {
int r = (int) sqrt(1.0 * n);
int sum = 0;
if (r * r == n) {
sum++;
r--;
}
for (int i = 1; i <= r; i++)
if (n % i == 0) {
sum += 2;
}
cout << sum << endl;
}
// 稍快于f1
int f2(int n){
int s = 1, r;
for (int i = 2; i * i <= n; i++) {
r = 0;
while (n % i == 0) {
r++;
n /= i;
}
if (r > 0) {
r++;
s *= r;
}
}
if (n > 1)
s *= 2;
cout << s << endl;
}
ll f3(ll n) {
ll res=1;
for(ll i=2;i*i<=n;i++){
ll k=0;
while(n%i == 0){
n = n/i;
k++;
}
if(k) res *= (k+1);
}
if(n != 1) res=res*2;
if(res==1){
if(n==1) return 1;
else return 2;
}
cout << res << endl;
}约数和定理
对于一个大于1正整数n可以分解质因数：
则由约数个数定理可知n的正约数有
定理证明
若n可以分解质因数：
可知
....
同理可知，
实际上n的约数是在
由乘法原理可知它们的和为
例
例：正整数360的所有正约数的和是多少？
解：
将360分解质因数可得
由约数和定理可知，360所有正约数的和为
可知360的约数有：
则它们的和为：
实现
ll qpow(ll x, ll y) {
ll res = 1;
while (y) {
if (y & 1) res *= x;
x *= x;
y >>= 1;
}
return res;
}
ll getsum(ll n) {//返回n的约数和是多少.
ll res = 1;
for (ll i = 2; i * i <= n; i++) {
ll k = 0;
while (n % i == 0) {
n = n / i;
k++;
}
res *= ((1 - qpow(i, k + 1)) / (1 - i));
} //用等比数列公式(快速幂)算.
if (n != 1) res *= (1 + n);
cout << res << endl;
}题目
求正约数应用例题hihocoder – 1284
直接暴力肯定不行, 所以想到求他们的约数, 则n的约数*m的约数/GCD(n,m)的约数就是答案. 求约数用以上定理.
ll getnum(ll n) { //得到a的约数个数.
ll res = 1;
for (ll i = 2; i * i <= n; i++) {
ll k = 0;
while (n % i == 0) {
n = n / i;
k++;
}
if (k) res *= (k + 1);
}
if (n != 1) res = res * 2; //最后一个素数.
if (res == 1) { //本身就是素数或1.
if (n == 1) return 1;
else return 2;
}
return res;
}
void solve(ll n, ll m) {
ll k = __gcd(m, n);
ll num1 = getnum(n);
ll num2 = getnum(m);
ll num3 = getnum(k);
ll t = __gcd(num3, num1 * num2);
printf("%lld %lld\n", 1ll * num1 * num2 / t, 1ll * num3 / t);
}