LCM的个数
Time Limit: 1000ms Memory limit: 65536K 有疑问?点这里^_^
题目描述
对于我们来说求两个数的LCM(最小公倍数)是很容易的事,现在我遇到了一个问题需要大家帮助我来解决这问题,问题是:给你一个数n,然后统计有多少对(a<=b) LCM(a,b)=n;例如LCM(a,b)=12; 即(1,12),(2,12),(3,12),(4,12),(6,12),(12,12),(3,4),(4,6);
输入
输入数组有多组,每组数据包含一个整数n(n<=10^9);
输出
输出每组数据的对数。
示例输入
2346
示例输出
2235#include <stdio.h>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int Max=100000;
int a[100000];
int top;
int GCD(int a,int b)
{
return b==0?a:GCD(b,a%b);
}
int main()
{
int n;
int sum;
while(~scanf("%d",&n))
{
top=0;
for(int i=1; i*i<=n; i++)
{
if(n%i==0)
{
a[top++]=i;
if(n/i!=i)
a[top++]=n/i;
}
}
sort(a,a+top);
sum=0;
for(int i=0; i<top; i++)
{
for(int j=i; j<top; j++)
{
int ans=GCD(a[i],a[j]);
if(a[j]/ans*a[i]==n)
{
sum++;
}
}
}
printf("%d\n",sum);
}
return 0;
}
版权声明:本文为博主原创文章,未经博主允许不得转载。