首页 > 代码库 > hdu1492(约数个数定理)
hdu1492(约数个数定理)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1492
这里先讲一下约数个数定理:
对于正整数x,将其质因分解为 x = pow(p1, a) * pow*(p2, b) * pow(p3, c) * ...
则其约数个数为:num(x) = (a+1) * (b+1) * (c+1) *...
推导:
由约数定义可知p1^a1的约数有:p1^0, p1^1, p1^2......p1^a1 ,共(a1+1)个;同理p2^a2的约数有(a2+1)个......pk^ak的约数有(ak+1)个。
故根据乘法原理:n的约数的个数就是(a1+1)(a2+1)(a3+1)…(ak+1)。
那么这道题直接代这个公式好啦~
题意:
给出一个64bit的数,求它的约数的个数;
代码:
1 #include <iostream>
2 #include <stdio.h>
3 #define ll long long
4 using namespace std;
5
6 int main(void){
7 ll n;
8 while(scanf("%lld", &n)&&n){
9 int a[4]={1, 1, 1, 1};
10 int b[4]={2, 3, 5, 7};
11 for(int i=0; i<4; i++){
12 while(n%b[i]==0){
13 a[i]++;
14 n/=b[i];
15 }
16 }
17 printf("%d\n", a[0]*a[1]*a[2]*a[3]);
18 }
19 return 0;
20 }
hdu1492(约数个数定理)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。