UVA 10892 LCM Cardinality Solution
Solution in c++:
///**********ALLAH IS ALMIGHTY************///
///AH Tonmoy
///Department of CSE,23rd batch
///Islamic University,Bangladesh
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
#define int64 long long
#define pb push_back
using namespace std;
int64 GCD(int64 m, int64 n)
{
if (m == 0)
return n;
return GCD(n % m, m);
}
int64 LCM(int64 m, int64 n)
{
return (m*n / GCD(m, n));
}
main()
{
int n, nn, c,i,j;
vector<int>div;
while (scanf("%d", &n))
{
if(n==0)
break;
div.clear();
nn = (int)sqrt(n);
for (int i=1; i<=nn; i++)
if (n%i==0)
{
div.pb(i);
div.pb(n/i);
}
if (nn*nn==n)
div.pop_back();
nn = div.size();
c = 0;
for(i=0; i<nn; i++)
for(j=i; j<=nn-1; j++)
if (LCM(div[i], div[j])==n)
c++;
printf("%d %d\n", n, c);
}
}
///**********ALLAH IS ALMIGHTY************///
///AH Tonmoy
///Department of CSE,23rd batch
///Islamic University,Bangladesh
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
#define int64 long long
#define pb push_back
using namespace std;
int64 GCD(int64 m, int64 n)
{
if (m == 0)
return n;
return GCD(n % m, m);
}
int64 LCM(int64 m, int64 n)
{
return (m*n / GCD(m, n));
}
main()
{
int n, nn, c,i,j;
vector<int>div;
while (scanf("%d", &n))
{
if(n==0)
break;
div.clear();
nn = (int)sqrt(n);
for (int i=1; i<=nn; i++)
if (n%i==0)
{
div.pb(i);
div.pb(n/i);
}
if (nn*nn==n)
div.pop_back();
nn = div.size();
c = 0;
for(i=0; i<nn; i++)
for(j=i; j<=nn-1; j++)
if (LCM(div[i], div[j])==n)
c++;
printf("%d %d\n", n, c);
}
}
No comments