Problem 1060 : No Story

Problem J: No Story
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1060&lang=jp

• 問題概要

LCM(a, b) = L となるような正の整数 a, b (a ≤ b) の組み合わせはいくつか。

• 解法

Lを素因数分解する。
約数を全列挙する。
LCMとは何かということを考えながら、その約数とセットになるとLCMがLになるようなbの数の合計を数える。

a < b , b> aのとき両方のときを数えてるので２で割る、ただし、a==b(つまり=L)のときは一回しか足されてないので、１を足して２で割る。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(long long int  i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)


const long long int  MAX  = 1000001;
bool p[MAX];
using namespace std;

vector<long long int > primeFactor( long long int  n ){
  vector<long long int > v;
  rep(i, sqrt(n)+1){
    if(!p[i])continue; 
    if( n % i != 0 )continue;
    long long int  cnt = 1;
    n /= i;
    while( n % i == 0){
      n /= i;
      cnt++;
    }
    v.push_back(cnt);
  }  
  if( n != 1 ) v.push_back(1);
  return v;
}

long long int  solve(vector<long long int > &pf, long long int  now, vector<long long int > &comb){
  if(now == pf.size()){
    long long int  tmp = 1;
    rep(i, pf.size()){
      if(pf[i] == comb[i]){
	tmp *= pf[i] + 1;
      }
    }
    return tmp;
  }
  long long int  sum = 0;
  rep(i, pf[now] + 1){
    comb.push_back(i);
    sum += solve(pf, now+1, comb);
    comb.pop_back();
  }
  return sum;
}

main(){
  rep(i, MAX)p[i] = true;
  p[0] = p[1] = false;
  rep(i, sqrt(MAX)){
    if(!p[i])continue;
    for(long long int  j = 2; j * i < MAX; j++){
      p[i*j] = false;
    }
  }
 
  long long int  l;
  while( cin >> l ){
    if( l == 0)break;
    vector<long long int > pf = primeFactor(l), comb;
    cout << ( solve(pf, 0, comb) + 1) / 2 << endl;
  }
}