首页 > 代码库 > LCM Cardinality 暴力
LCM Cardinality 暴力
Description
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 LCMof (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 theLCM cardinality of that number N. In this problem your job is to find out the LCM cardinality of a number.
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.
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.
Sample Input Output for Sample Input
2 12 24 101101291 0 | 2 2 12 8 24 11 101101291 5 |
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<math.h> 5 #include<iostream> 6 #include<algorithm> 7 using namespace std; 8 int gcd(int x,int y) 9 { 10 if(y==0)return x; 11 return gcd(y,x%y); 12 } 13 int lcm(int x,int y) 14 { 15 return x/gcd(x,y)*y; 16 } 17 long long c[500]; 18 int main() 19 { 20 int n,nu,i,j,size,ans; 21 while(scanf("%d",&n),n) 22 { 23 ans=nu=0; 24 size=sqrt(n+0.5); 25 for(i=1; i<=size; i++) 26 { 27 if(n%i==0) 28 { 29 c[nu++]=i; 30 if(i*i!=n) 31 c[nu++]=n/i; 32 } 33 } 34 for(i=0; i<nu; i++) 35 { 36 for(j=i; j<nu; j++) 37 if(lcm(c[i],c[j])==n)ans++; 38 } 39 cout<<n<<" "<<ans<<endl; 40 } 41 }