SRM394 Div2 1000

問題

0より大きい整数kは、mより小さく、mを割り切れるが、k^nではmを割り切れないとき、「mのcool divisor」という。d(m)は、整数mでのcool divisorの数とする。整数a,bについて、d(a)+d(a+1)+...+d(a+b)の値を返す。

1<=a<=10^6
1<=b<=10^7
2<=n<=10

考え方

総和について、視点を変えて、「x以下でkが約数の個数はx/k(=xをkで割った整数部分)」という事実を知っているかどうか。

(aからa+bまでの約数の個数)-(そのn乗での約数の個数)で計算できる。
■aからa+bまでの約数の個数
約数の個数を求めるために、「x以下でkが約数の個数は(x/k)」を用いて、

for(int k=2; k<=a+b; k++){ //k=1はそのn乗(==1)が割り切れるためcool divisorではない
  //(a+bまでの約数kの個数) - (a-1までの約数kの個数) == (aからa+bまでの約数kの個数)
  ret += ((a+b)/k) - ((a-1)/k);
  //k<mでなければならないので、
  //  kがa以上の時、k>=aのkの倍数の最後の値はcool divisorとしてありえない
  if(k>=a) ret--;
}

■そのn乗での約数の個数
上と同じ方法で、約数の個数を計算する。
k^nが約数のaからa+bまでの個数を求めるので、実際にk^nを計算して( (a+b)/k^n )-( (a-1)/k^n )がn乗での約数の個数になる。

反省

手も足もでなかった。
素因数分解で約数の個数を求めるのではなく、「x以下でkが約数の個数はx/k」をk=2,...でループを回して計算できる。