奇♂妙拆分(数学)
奇♂妙拆分
https://ac.nowcoder.com/acm/problem/14709
题目描述
在遥远的米♂奇♂妙♂妙♂屋里住着一群自然数，他们没事就喜欢拆♂开自己来探♂究。现在他们想知道自己最多能被拆分成多少个不同的自然数，使得这些自然数相乘的值等于被拆分的数。
输入描述:
第1行输入一个整数T，代表有T组数据。第2-T+1行，每行输入一个整数n，代表需要被拆分的数。数据保证：0<T≤100，0<n≤109。
输出描述:
输出一共T行，第i行输出一个整数，代表第i行输入的n最多可以被拆分成多少个不同的自然数。
示例1
输入
3 1 4 12
输出
1 2 3
说明
1可以被拆分为：1 4可以被拆分为：1*4（1*2*2是不允许的，因为有重复的数） 12可以被拆分为：1*2*6或1*3*4
示例2
输入
1 114514
输出
4
说明
114514可以被拆分为：1*2*31*1847
思路
类似于求一个数的质因子，把while改成了if，确保每个取到的因子各不相同。其中对于任意的x，其最优展开式有且只有一个数大于
，所以在最后把ans + 1。
代码
//奇♂妙拆分(数学)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int t , num;
scanf("%d" , &t);
while(t--)
{
scanf("%d" , &num);
int ans = 0;
for(int i = 1 ; i * i < num ; i++)
{
if(num % i == 0)
{
num /= i;
ans++;
}
}
printf("%d\n" , ans + 1);
}
return 0;
} 牛客算法竞赛入门课第一节习题题解 文章被收录于专栏
入门课第一节习题题解
投递美团等公司10个岗位
巨人网络成长空间 50人发布