n的约数(约数统计+dfs)

2018年03月31日 11点热度 0人点赞 0条评论

链接:https://www.nowcoder.com/acm/contest/82/A
来源:牛客网

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

t次询问,每次给你一个数n,求在[1,n]内约数个数最多的数的约数个数

输入描述:

第一行一个正整数t
之后t行,每行一个正整数n

输出描述:

输出t行,每行一个整数,表示答案
示例1

输入

5
13
9
1
13
16

输出

6
4
1
6
6

备注:

对于100%的数据,t <= 500 , 1 <= n <= 1000000000000000000
/*首先给出一个简单的求因子个数的公式
设n=p1^k1*p2^k2*……*pn^kn,其中p1,p2,……,pn为互不相同的质数,k1,k2,……,kn为正整数(这叫n的标准分解)
则n所有正约数个数为(k1+1)(k2+2)*……*(kn+1)个
15464=2^3*1933
正约数为(3+1)*(1+1)=8个
然后给出一个溢出的相关的知识:当整型数据超出取值范围时 数据呈环形变化 例如32767 + 1 = -32768 36767 +2 = -32767
因为比较情况比较复杂,于是本题防溢出的方式不是这个。。。
*/
//很容易想到,因子2的个数要大于等于3的个数,等等。然后情况不是很多,dfs即可。
//时间复杂度不好算,但是可以用计算机可以计算出最大枚举34136个数
#include
#include
#include
#define ll long long
using namespace std;
int p[20] = {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47},T;
ll n;
int dfs(ll num,int pos,int k,int ans) { //num为当前的数值,pos为当前素数的位置,k为当前素数的个数,ans为当前因子的个数
	if(pos>15) return 0;
	int ret=ans;
	for(int i=1; i<=k; ++i) {
		if(n/p[pos]
未经允许不得转载!n的约数(约数统计+dfs)

update

纸上得来终觉浅, 绝知此事须躬行。