定義
在數論裡，某一正整數的質因子指能整除該數的質數整數。
相關定理
任何一個大于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:24=(1*2,1*2^2)sum=1+(2)+(4);//2*2
2:3612,91836sum=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
上面這個方法要100s,題目要求不是求因子和，所以如果有質數在[a,b]内，那麼最大的質數就是answer
主要的函數：
cal(x)求x的因子和
intcal(inta)//計算a的因子和
{
inti;
intlast,now;//sum
last=1;now=0;
intx;//因子的^x與前一階段
intt=a;
for(i=0;primes[i]<=a;i++)
{
if(a%primes[i]==0)
{
x=last;
now=last;
while(a%primes[i]==0)
{
//printf("%dcandiv%d:",a,primes[i]);//debug
a/=primes[i];
x*=primes[i];
now+=x;
//printf("now:%dx:%dn",now,x);//debug
}
//printf("now:%dlast:%dn",now,last);//debug
last=now;
}
}
returnlast-t;
//printf("answeris%dn",last);
}
第二個DP雖然TLE，但是感覺有思考價值，求很多數的因子和時，也許能用的到
voidwork2()
{
inti,j;
dp[1]=1;
inttemp;
for(i=2;i<=1000000;i++)
{
for(j=0;primes[j]<=i;j++)//尋找上一層
if(i%primes[j]==0)
break;
inti2=i;
temp=1;//求前面那個系數
while(i2%primes[j]==0)
{
temp=temp*primes[j]+1;
i2/=primes[j];
}
intlast=dp[i2];
dp[i]=temp*last;
//printf("dp[%d]=%dn",i,dp[i]);
if(i%1000==0)cout<
}
}
相關拓展
子模塊電容電壓均衡控制策略是保證模塊化多電平換流器（modularmultilevelconverter,MMC）正常運行的重要環節。對于每相橋臂含有大規模數量子模塊的模塊化多電平換流器高壓直流輸電（modularmultilevelconverterbasedhighvoltagedirectcurrent,MMC-HVDC）系統,減小排序複雜度對MMC-HVDC工程控制器設計難度以及硬件需求的降低具有重要意義。
該文基于質因子分解法提出一種優化的混合排序法,通過引入希爾排序算法大幅度降低排序次數,從而降低仿真時間,降低了對系統硬件的要求。推導适用于MMC-HVDC系統的希爾排序步長的時間複雜度,給出基于混合排序法的排序次數計算公式,分析分組層數對系統降低頻率的影響,得到分組層數與混合排序法優化效率成反比例關系的結論。最後在PSCAD/EMTDC中搭建兩端401電平MMC-HVDC模型進行仿真,仿真結果驗證了混合排序法及分組層數對優化效率影響的分析的有效性與正确性。
