质因子的算法

发布网友

我来回答

共1个回答

热心网友

求因子和的方法：
sqrt( n ) 太慢，可以用一下DP的思想，
把质因子分析出来 ai^x，
那么 再乘 一个 ai+1 ，因子和就增加了原来的 ai+1 倍
如果这个质因子是2次幂，那么还得增加原来那一层的 (ai+1)^2倍
速度因该是质因子的指数的和，但是受到求质因子速度的制约
36:
0: 1
1: 2 4 =( 1*2,1*2^2 ) sum = 1+(2)+(4); //2*2
2: 3 6 12 , 9 18 36 sum = 1+2+4+ (3+6+12) + (9+18+26)
也就是说，如果我们知道了一层的sum，那么就可以推出下一层的sum
知道了一个数的因子和，就可以推知他的质数倍^x 的那个数的因子的和，
DP来解决这道题，对于数 x，把它除尽一个质数，那么x/a^k = y
那么 y 就是上一层的那个sum
而对于x，存在 x = (1+a+a^2+a^3..a^k)*y
上面这个方法要 100 s, 题目要求不是求因子和，所以如果有质数在 [a,b] 内，那么最大的质数就是answer
主要的函数：
cal (x) 求 x 的因子和
int cal(int a) //计算 a 的因子和
{
int i;
int last,now;// sum
last = 1;now = 0;
int x;// 因子的^x 与前一阶段
int t = a;
for ( i=0;primes[ i ] <= a;i++ )
{
if ( a%primes[ i ] == 0 )
{
x = last;
now = last;
while ( a %primes[ i ] == 0 )
{
// printf(%d can div %d :, a ,primes[i] );//debug
a /= primes[i];
x *= primes[ i ];
now += x;
// printf(now: %d x: %d\n,now,x);//debug
}
// printf(now: %d last: %d\n,now,last);//debug
last = now;
}
}
return last - t;
// printf(answer is %d\n,last);
}
第二个DP虽然TLE，但是有思考价值，求很多数的因子和时，也许能用的到
void work2()
{
int i,j;
dp[ 1 ] = 1;
int temp;
for ( i=2;i<=1000000;i++ )
{
for ( j=0; primes[ j ]<=i;j++ ) //寻找上一层
if ( i % primes[ j ] == 0 )
break;
int i2 = i;
temp = 1;//求前面那个系数
while ( i2 % primes[ j ] == 0 )
{
temp = temp* primes[ j ] + 1;
i2 /= primes[ j ];
}
int last = dp [ i2 ];
dp [ i ] = temp* last;
// printf(dp[ %d ] = %d\n,i,dp[i]);
if (i%1000 == 0) cout<<i<<endl;//debug
}
}