質因子

質因子-定義

在數論里，某一正整數的質因子指能整除該數的質數整數。

相關的定理

任何一個大於1的自然數N，都可以唯一分解成有限個質數的乘積 N=(P_1^a1)*(P_2^a2)......(P_n^an) , 這裡P_1<...

這樣的分解稱為N 的標準分解式。

質因子-求質因子和的算法

求因子和的方法：

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<<

}

}