山东理工大学第七届ACM校赛-LCM的个数 分类: 比赛 2015-06-26 10:37 18人阅读 评论(0) 收藏

时间:2022-03-23 06:54:21

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;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。