题目描述

在遥远的米♂奇♂妙♂妙♂屋里住着一群自然数，他们没事就喜欢拆♂开自己来探♂究。现在他们想知道自己最多能被拆分成多少个不同的自然数，使得这些自然数相乘的值等于被拆分的数。

输入描述

第1行输入一个整数T，代表有T组数据。
第2-T+1行，每行输入一个整数n，代表需要被拆分的数。
数据保证：0<T≤100，0<n≤109。

输出描述

输出一共T行，第i行输出一个整数，代表第i行输入的n最多可以被拆分成多少个不同的自然数。

题目思路

本题带有一点贪心的思想。
即从最小的数开始，对小于等于n的数进行遍历；同时不断改变n的值，即

for(int i = 2; i <= n ;i++)
{
    if(n % i == 0 && i * i != n)//注意，由于不能出现相同因数，故需要判断i * i != n
    {
        cont++;
        n /= i;
    }
}

完整代码

#include<stdio.h>
#include<string>
#define ll long long
using namespace std;
ll n;
int t;
int main()
{
    scanf("%d",&t);
    while (t--)
    {
        scanf("%lld",&n);
        ll temp = n;
        ll cont = 1;
        for(int i = 2; i <= n ;i++)
        {
            if(n % i == 0 && i * i != n)
            {
                cont++;
                n /= i;
            }
        }
        if(cont == 1 && temp != 1) cont++;    
        printf("%d\n", cont);
    }
}

总结

刚开始看这道题时，一见到求最大值就直奔动态规划，发现复杂度高（O(N^2)）。因此这种和因数相关的题目还是直接遍历，通过改变上界求解比较容易。动归可以在求加数时使用。