PKU 2917 Diophantus of Alexandria

http://poj.org/problem?id=2917
ある整数n(1<=10^9)が与えられる。
この時、 $\frac{1}{x}+\frac{1}{y}=\frac{1}{n} \hspace{10} (x \leq y)$ を満たすような整数x,yの組の個数を求めろというような問題。

結構苦労して答えを思いつけたので適当な説明を書きたいと思います。

まず、 $\frac{1}{x}+\frac{1}{y}=\frac{1}{n}$ を式変形すると、

$x=\frac{yb}{y-n}$ となります。
ここで $b=n+k$ とおくと、
$x=\frac{n^2}{k}+k$ というふうになり、ここでxが整数となるような条件は、kがn^2の約数であればいいので、n^2の約数の個数を求めます。
ただ、愚直にO(sqrt(n^2))でやると間に合わないので、約数の個数を求める数式をちょっと考えて変更します。
約数の個数は、
$n={p_1}^{e_1} {p_2}^{e_2} {p_3}^{e_3} \ldots$ (pは素数)のとき、
$(1+e_1)(1+e_2)(1+e_3) \ldots$ で表されます。
ここでn^2はe_kが2倍になっているだけなので、n^2の約数の個数は
$(1+2e_1)(1+2e_2)(1+2e_3) \ldots$ となり、O(sqrt(n))で計算することが出来ます。

ll divi2(int in){
  ll ret=1;
  for(int i=2;i*i<=in;++i){
    int p=1;
    while(in%i==0){
      in/=i;
      p+=2;
    }
    ret*=p;
  }
  if(in>1)ret*=3;
  return ret;
}

main(){
  int t;
  cin>>t;
  rep(sc,t){
    cout<<"Scenario #"<<sc+1<<":"<<endl;
    int in;
    cin>>in;
    cout<<(divi2(in)+1)/2<<endl;
    cout<<endl;
  }
}