首页 > 代码库 > ZOJ 2562 More Divisors(高合成数)
ZOJ 2562 More Divisors(高合成数)
ZOJ 2562 More Divisors(高合成数)
ACM
题目地址:ZOJ 2562 More Divisors
题意:
求小于n的最大的高合成数,高合成数指一类整数,不论什么比它小的自然数的因子数目均比这个数的因子数目少。
分析:
网上都叫它反素数,事实上我查了一下,翻素数应该是正着写倒着写都是素数的素数。这个应该叫高合成数,见Wikipedia: Highly composite number
高合成数有下面特征:
where
Any factor of n must have the same or lesser multiplicity in each prime:
所以用回溯枚举。
代码:
/* * Author: illuz <iilluzen[at]gmail.com> * Blog: http://blog.csdn.net/hcbbt * File: 2562.cpp * Create Date: 2014-08-06 20:45:53 * Descripton: Highly Composite Number */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define repf(i,a,b) for(int i=(a);i<=(b);i++) typedef long long ll; const int M = 1000; ll n; ll bestNum; ll bestSum; ll hcm[M][2]; ll prim[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67}; // current is num, use the prim[k], sum of divisors, the limit of prim[k] you can use void getNum(ll num, int k, ll sum, int limit) { if (sum > bestSum) { bestSum = sum; bestNum = num; } else if (sum == bestSum && num < bestNum) { bestNum = num; } ll p = prim[k]; for (int i = 1; i <= limit; i++, p *= prim[k]) { // use i prim[k]s if (num * p > n) break; getNum(num *= prim[k], k + 1, sum * (i + 1), i); } } // clac log2(n) int log2(ll n) { int ret = 0; ll p = 1; while (p < n) { p <<= 1; ret++; } return ret; } // return the number of Highly Composite Number in [1, n] // and save the HCM in hcm[][2] int gethcm() { int ret = 0; n = 500000; // [1, n] while (n > 0) { bestNum = 1; bestSum = 1; getNum(1, 0, 1, log2(n)); cout << bestNum << ' ' << bestSum << endl; hcm[ret][0] = bestNum; hcm[ret][1] = bestSum; n = bestNum - 1; ret++; } return ret; } int main() { while (cin >> n) { bestNum = 1; bestSum = 1; getNum(1, 0, 1, 50); cout << bestNum << endl; } }
ZOJ 2562 More Divisors(高合成数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。