最小公倍数最大集

NC214465. 最小公倍数最大集

描述

给定一个正整数n,求最大的集合，满足集合中任意两个数的最小公倍数都等于n。

只需输出这个最大的集合包含的元素个数即可。

(集合中任意两个元素不相同，保证数据范围内所有答案大于等于2)

输入描述

输入一行一个正整数

输出描述

输出一行一个整数代表答案

示例1

输入:

输出:

说明:

第一组样例可能的集合为{3,4,12}

3,4的最小公倍数为12。

3,12的最小公倍数为12。

12,4的最小公倍数为12。

示例2

输入:

32592951

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 2ms, 内存消耗: 380K, 提交时间: 2020-12-19 19:45:24

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
    ll n;
    cin>>n;
    ll ans=1;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0)ans++;
        while(n%i==0)n/=i;
    }if(n>1)ans++;
    printf("%d",ans==1?0:ans);
}

上一题

下一题

详情