Problem F LCM Cardinality Input: Standard Input
Output: Standard Output
Time Limit: 2 Seconds
A pair of numbers has a unique LCM but a single number can be the LCM of more than one possible pairs. For example 12 is the LCM of (1, 12), (2, 12), (3,4) etc. For a given positive integer N, the number of different integer pairs with LCM is equal to N can be called the LCM cardinality of that number N. In this problem your job is to find out the LCM cardinality of a number.
<!--[if !supportEmptyParas]--> <!--[endif]-->
Input
The input file contains at most 101 lines of inputs. Each line contains an integer N (0<N<=2*109). Input is terminated by a line containing a single zero. This line should not be processed.
<!--[if !supportEmptyParas]--> <!--[endif]-->
Output
For each line of input except the last one produce one line of output. This line contains two integers N and C. Here N is the input number and C is its cardinality. These two numbers are separated by a single space.
<!--[if !supportEmptyParas]--> <!--[endif]-->
Sample Input Output for Sample Input
2 12 24 101101291 0 |
2 2 12 8 24 11 101101291 5 |
#include <iostream>
#include <stdio.h>
#include <queue>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <map>
#include <stack>
#include <math.h>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std ;
typedef long long LL ;
const int M= ;
bool isprime[M+] ;
int prime[M] ,id;
void make_prime(){
id= ;
memset(isprime,,sizeof(isprime)) ;
for(int i=;i<=M;i++){
if(!isprime[i])
prime[++id]=i ;
for(int j=;j<=id&&prime[j]*i<=M;j++){
isprime[i*prime[j]]= ;
if(i%prime[j]==)
break ;
}
}
}
LL gao(LL x){
LL sum ;
LL ans= ;
for(int i=;i<=id&&prime[i]*prime[i]<=x;i++){
if(x%prime[i]==){
sum= ;
while(x%prime[i]==){
sum++ ;
x/=prime[i] ;
}
ans=ans*(sum+sum+) ;
}
if(x==)
break ;
}
if(x!=)
ans*= ;
return (ans+)>> ;
}
int main(){
LL x ;
make_prime() ;
while(cin>>x&&x){
cout<<x<<" "<<gao(x)<<endl ;
}
return ;
}