LCM Cardinality

暴力    

// File Name: uva10892.cpp  
// Author: bo_jwolf  
// Created Time: 2013年09月16日 星期一 22:32:26  
  
#include<vector>  
#include<list>  
#include<map>  
#include<set>  
#include<deque>  
#include<stack>  
#include<bitset>  
#include<algorithm>  
#include<functional>  
#include<numeric>  
#include<utility>  
#include<sstream>  
#include<iostream>  
#include<iomanip>  
#include<cstdio>  
#include<cmath>  
#include<cstdlib>  
#include<cstring>  
#include<ctime>  
  
using namespace std;  
  
vector<int> Q ;  
long long n ;  
  
long long gcd( long long a , long long b )   
{  
    return b == 0 ? a : gcd( b , a % b ) ;  
}  
  
long long lcm( long long a , long long b )  
{  
    return ( 1LL*a * b ) / gcd( a , b ) ;  
}  
  
int main()  
{   
    while( scanf( "%lld" , &n ) != EOF )  
    {  
        if( n == 0 )  
            break ;  
        Q.clear() ;  
        for( long long i = 1 ; i <= sqrt( n ) ; ++i )  
        {  
            if( n % i == 0 )  
            {  
                if( n / i != i )  
                {  
                    Q.push_back( n / i ) ;   
                    Q.push_back( i ) ;  
                }  
                else  
                {  
                    Q.push_back( i ) ;  
                }  
            }  
        }  
        long long len = Q.size() ;  
        long long ans = 1 ;   
        for( long long i = 0 ; i < len ; ++i )  
        {  
            for( long long j = i + 1 ; j < len ; ++j )  
            {  
                if( lcm( Q[ i ] , Q[ j ] ) == n )   
                        ans++ ;  
            }  
        }  
        printf( "%lld %lld\n" , n , ans ) ;  
    }  
return 0;  
}