最复杂的数(约数个数定理+反素数性质)

发布于:2021-10-26 16:57:15

约数个数定理
编辑


对于一个大于1正整数n可以
分解质因数:

?




则n的
正约数的个数就是

?
?



其中a
1、a
2、a
3…a
k是p
1、p
2、p
3,…p
k的指数。



定理简证
编辑


首先同上,n可以
分解质因数:n=p1^a1×p2^a2×p3^a3*…*pk^ak,


由约数定义可知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)。







例题
编辑


例题:正整数378000共有多少个
正约数?


解:将378000
分解质因数378000=2^4×3^3×5^3×7^1


由约数个数定理可知378000共有正约数(4+1)×(3+1)×(3+1)×(1+1)=160个。
? ? ??
反素数


对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0




性质
编辑


性质一:一个反素数的质因子必然是从2开始连续的
质数.


性质二:p=2^t1*3^t2*5^t3*7^t4.....必然t1>=t2>=t3>=....
? ? ? ?


例题:





1060?最复杂的数



题目来源:?
Ural?1748


基准时间限制:1?秒 空间限制:131072?KB 分值:?40?
难度:4级算法题





?收藏



?关注





把一个数的约数个数定义为该数的复杂程度,给出一个n,求1-n中复杂程度最高的那个数。


例如:12的约数为:1 2 3 4 6 12,共6个数,所以12的复杂程度是6。如果有多个数复杂度相等,输出最小的。






Input

第1行:一个数T,表示后面用作输入测试的数的数量。(1?<=?T?<=?100)
第2?-?T?+?1行:T个数,表示需要计算的n。(1?<=?n?<=?10^18)

Output

共T行,每行2个数用空格分开,第1个数是答案,第2个数是约数的数量。

Input示例

5
1
10
100
1000
10000

Output示例

1?1
6?4
60?12
840?32
7560?64





相关问题



最复杂的数?V2?

320
?









李陶冶?
(题目提供者)









#include
typedef long long ll;
ll ans,maxsum,n;
int p[20]={1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
void dfs(ll num,ll k,ll sum,ll limits)
{
//num表示当前枚举到的数
//k表示枚举到的第k大的质因子
//sum表示该数的约数个数
//limits表示质因子个数上限
ll i,temp;
if(sum>maxsum)
{
maxsum=sum;
ans=num;//如果当前的数的约数个数更多,则更新当前数
}
if(sum==maxsum && num ans=num;//如果约数个数相同,将最优解更新为较小的数;
if(k>15)
return;
temp=num;
for(i=1;i<=limits;i++)
{
if(temp*p[k]/p[k]!=temp || temp*p[k]>n)//temp*a[k]/a[k]!=temp的条件是为了防止爆long long
break;
temp=temp*p[k];
dfs(temp,k+1,sum*(i+1),i);//继续下一步搜索
}
}
int main()
{
int T,i,j;
scanf("%d",&T);
while(T--)
{
ans=maxsum=0;
scanf("%lld",&n);
dfs(1,1,1,50);
printf("%lld %lld
",ans,maxsum);
}
}











相关推荐

最新更新

猜你喜欢