LCM Cardinality

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=31675#problem/E

暴力

// 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 , ans ) ;
	}
return 0;
}