NC14709 奇妙拆分

奇妙拆分

链接：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可以被拆分为：14（122是不允许的，因为有重复的数）
12可以被拆分为：126或13*4

拆分自然数

多个询问,每次给定一个自然数 $N$N,要求把 $N$N分解成多个不相等的自然数相乘x1*x2*x3...*xn

比如: 12=1*2*6或者12=1*3*4 最多3个不同的自然数

• 每个 $x_i$xi​肯定是从 $N$N的因子里面挑

• 贪心的挑选因子,先选小的一定比先选大的因子优(不知道对否,看别人的代码猜的)

• 所以从小到大枚举因子累乘,复杂度 $O\left(能过\right)$O(能过)

  int ans = 0;
  for(int i=1; i<=n; i++) {
    if(n%i == 0) {
      ans ++;
      n /= i; //每次选择因子i后缩小n的范围
    }
  }
  

完整代码

//#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif


#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)
void err() { cout << "\033[39;0m" << endl; }
#endif

template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

int n, m, Q, K;

int main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	scanf("%d ", &Q);
	while(Q--) {
		scanf("%d ", &n);
		int ans = 0;
		for(int i=1; i<=n; i++) {
			if(n%i == 0) {
				ans ++;
				n /= i;
			}
		}
		printf("%d\n", ans);
	}

#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}