主题：第38次编程比赛第一题题目
liangbch [专家分：1270] 发布于 2006-08-18 12:16:00
在N以内(小于等于N)找出一个数，要求：
1.这个数的约数的个数达到最大，
2.如果有好几个数满足条件1，仅取最小的那个数
说明：
1) 1<N<=[color=FF0000]2^32-1[/color]，每个N的时限是1000ms。内存限制256M,注意使用适当数据类型，以免溢出。
函数原型：
// n: 范围
// result:结果，存放符合条件的那个数
// count:存入存放符合条件的那个数的约数的个数
// arr:存放那个数的所有约数，按照从小到大的顺序
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[]);
例：
n=100， 则 result=60,
在100以内，60和90的约数个数同为12个，达到这个范围内所有整数中，其约数个数的最大值，但60比90小，所有正确答案为60。60共有12个约数：1,2,3,4,5,6,10.12.15.20.30,60.所以count应该存入12，从arr[0]开始，应该依次写入1,2,3,4,5,6,10.12.15.20.30,60。
回复列表 （共47个回复）
11 楼
boxertony [专家分：23030] 发布于 2006-08-18 19:49:00
// 统计n的约数个数，并得到n的质因子
// factors[]--n的质因子
// factorCount[]-- 每个质因子的数量
// numFactors -- n的质因子个数
int countDivisor(long n, long factors[], long factorCount[], long &numFactors)
{
int nCount = 1;
int temp = 0;
if(n <= 1)
return nCount;
while((n&1) == 0)
{
n >>= 1;
++temp;
}
nCount *= temp + 1;
numFactors = 0;
if(temp > 0)
{
factors[numFactors] = 2; // 存放具体的素因子
factorCount[numFactors++] = temp; // 存放每个素因子的个数
}
int nSqrt = (int)sqrt((double)n+0.1);
long nPrimesCount = 0;
long *pPrimes = new long[nSqrt+1];
assert(pPrimes != NULL);
nPrimesCount = GetPrimes(nSqrt, pPrimes);
bool bIsPrime = true; // 判断n是否素数
for(int i=1; i<nPrimesCount; ++i)
{
if(n < pPrimes[i])
{
break;
}
temp = 0;
while(n%pPrimes[i] == 0)
{
++temp;
n /= pPrimes[i];
bIsPrime = false;
}
nCount *= temp + 1;
if(temp > 0)
{
factors[numFactors] = pPrimes[i];
factorCount[numFactors++] = temp;
}
}
if(n > 1)
{
nCount *= 2;
factors[numFactors] = n;
factorCount[numFactors++] = 1;
}
delete []pPrimes;
if(nCount == 1 && bIsPrime == true)
nCount = 2;
return nCount;
}
12 楼
boxertony [专家分：23030] 发布于 2006-08-18 19:49:00
// 根据某个数的质因子分解结果产生所有的约数
// *result -- 存放约数
// count -- 统计约数个数
// factors[]--质因子
// factorCount[]-- 每个质因子的数量
// numFactors -- 质因子个数
// value -- 约数（用于计算约数）
void GenerateDivisors(unsigned long *result, int &count, long factors[], long factorCount[], long numFactors, long &value)
{
long i;
long oldvalue;
if(numFactors <= 0)
{
result[count++] = value;
return;
}
oldvalue = value;
GenerateDivisors(result, count, factors, factorCount, --numFactors, value);
value = oldvalue;
for(i=0; i<factorCount[numFactors]; i++)
{
value *= factors[numFactors];
oldvalue = value;
GenerateDivisors(result, count, factors, factorCount, numFactors, value);
value = oldvalue;
}
}
// n: 范围
// result:结果，存放符合条件的那个数
// count:存入存放符合条件的那个数的约数的个数
// arr:存放那个数的所有约数，按照从小到大的顺序
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[])
{
unsigned long i;
assert(n >= 1);
if(n == 1)
{
*result = 1;
*count = 1;
arr[0] = 1;
return ;
}
int temp;
long factors[20]; // 存储n的质因子
long factorCount[20]; // 每个质因子的个数
long numFactors = 0; // n的质因子个数
long value;
int step; // 循环步长（目的：提高速度）
unsigned long start;
if(n < 12)
step = 2;
else if(n < 120)
step = 12;
else if(n < 1680)
step = 60;
else if(n < 2520)
step = 120;
else if(n < 55440)
step = 2520;
else if(n < 720720)
step = 27720;
else if(n < 61261200)
step = 360360;
else
step = 6126120;
start = 0;
while(start <= n)
start += step;
start -= step;
*count = 0;
*result = 0;
for(i=start; i>=n/2; i-=step)
{
temp = countDivisor(i, factors, factorCount, numFactors);
if(temp >= *count)
{
*count = temp;
*result = i;
temp = 0;
value = 1;
// 产生该数的所有约数
GenerateDivisors(arr, temp, factors, factorCount, numFactors, value);
}
}
qsort((void*)arr, *count, sizeof(unsigned long), cmp);
}
13 楼
szh [专家分：380] 发布于 2006-08-18 20:33:00
//编译器Dev-C++
//计算n的公约数数目
int ComputeNum(unsigned long n)
{
unsigned long big=n, small=0;
int count = 2;
for( small = 2; small < big; small++)
{
if(!(n%small))
{
big = n/small;
count += small == big ? 1: 2;
}
}
return count;
}
void AddArray(unsigned long n, int count, unsigned long arr[])
{
unsigned long big = n, small = 0;
int i=0, num = count - 1;
arr[i++] = 1;
arr[num--] = n;
for( small = 2; small < big; small++)
{
if(!(n%small))
{
big = n/small;
arr[i++] = small;
if( small != big )
arr[num--] = big;
}
}
}
void Search(unsigned long n, unsigned long *result, int *count, unsigned long arr[])
{
unsigned long i, k;
unsigned long m = (unsigned long)(n/2);
int temp, length;
*count = 2;
*result = 2;
length = n > 100 ? 10: 2;
k = n > 100 ? (unsigned long)(n/10)*10: (n%2? n-1: n);
for( i = k; i > m; i-=length)
{
if((temp=ComputeNum(i)) >= *count)
{
*count = temp;
*result = i;
}
}
AddArray(*result, *count, arr);
}
14 楼
boxertony [专家分：23030] 发布于 2006-08-18 21:55:00
// 重新修改了下，速度有了大幅度提高
// vc6下编译通过
int cmp(const void*x, const void *y)
{
return (*(int*)x - *(int*)y);
}
// 统计n的约数个数，并得到n的质因子
// factors[]--n的质因子
// factorCount[]-- 每个质因子的数量
// numFactors -- n的质因子个数
// 返回n的约数个数
long countDivisor(unsigned long n, unsigned long factors[], long factorCount[], long &numFactors)
{
int nCount = 1;
int temp = 0;
if(n <= 1)
{
numFactors = 1;
return nCount;
}
numFactors = 0;
// 质因子2的个数
while((n&1) == 0)
{
n >>= 1;
++temp;
}
if(temp > 0)
{
nCount *= temp + 1;
factors[numFactors] = 2; // 存放具体的素因子
factorCount[numFactors++] = temp; // 存放每个素因子的个数
}
// 对于有最大约数个数的数n（n<2^32），n的最大质因子必定不会超过29
long pPrimes[10] = {3, 5, 7, 11, 13, 17, 19, 23, 29};
for(int i=0; i<9; ++i)
{
if(n < pPrimes[i])
{
break;
}
temp = 0; // 统计n含有素数pPrimes[i]的个数
while(n%pPrimes[i] == 0)
{
++temp;
n /= pPrimes[i];
}
if(temp > 0)
{
nCount *= temp + 1;
factors[numFactors] = pPrimes[i];
factorCount[numFactors++] = temp;
}
}
if(n > 1)
{// 最后剩下一个质因子
nCount *= 2;
factors[numFactors] = n;
factorCount[numFactors++] = 1;
}
return nCount;
}
// 根据某个数的质因子分解结果产生所有的约数
// *result -- 存放约数
// factors[]--质因子
// factorCount[]-- 每个质因子的数量
// numFactors -- 质因子个数
void GenerateDivisors(unsigned long *result, unsigned long factors[],
long factorCount[], long numFactors)
{
long i, j, k;
long last_count, cur_count;
unsigned long temp;
result[0] = 1;
last_count = cur_count = 1;
for(i=0; i<numFactors; ++i)
{
temp = 1;
for(j=0; j<factorCount[i]; ++j)
{
temp *= factors[i];
for(k=0; k<last_count; ++k)
{
result[cur_count++] = result[k] * temp;
}
}
last_count = cur_count;
}
}
15 楼
boxertony [专家分：23030] 发布于 2006-08-18 21:56:00
// n: 范围
// result:结果，存放符合条件的那个数
// count:存入存放符合条件的那个数的约数的个数
// arr:存放那个数的所有约数，按照从小到大的顺序
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[])
{
unsigned long i;
assert(n >= 1);
if(n == 1)
{
*result = 1;
*count = 1;
arr[0] = 1;
return ;
}
long factorCount[20], max_factorCount[20]; // 每个质因子的个数
long numFactors = 0, max_numFactors; // n的质因子个数
long step; // 循环步长（目的：提高速度）
long temp;
unsigned long start;
if(n < 12)
step = 2;
else if(n < 120)
step = 12;
else if(n < 1680)
step = 60;
else if(n < 2520)
step = 120;
else if(n < 55440)
step = 2520;
else if(n < 720720)
step = 27720;
else if(n < 61261200)
step = 360360;
else
step = 6126120;
if(n > 4294410120)
start = 4294410120;
else
start = n/step*step;
*count = 0;
*result = 0;
for(i=start; i>=start/2; i-=step)
{
temp = countDivisor(i, factorCount, numFactors);
if(temp >= *count)
{
*count = temp;
*result = i;
// 复制该数的质因子的个数
max_numFactors = numFactors;
for(int j=0; j<numFactors; ++j)
{
max_factorCount[j] = factorCount[j];
}
}
}
// 产生该数的所有约数
unsigned long factors[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
GenerateDivisors(arr, factors, max_factorCount, max_numFactors);
qsort((void*)arr, *count, sizeof(unsigned long), cmp);
}
16 楼
wxq2300 [专家分：0] 发布于 2006-08-19 06:24:00
先看下，还没想好！
17 楼
magicalking [专家分：150] 发布于 2006-08-19 11:54:00
#include <iostream>
using namespace std;
inline void Search(unsigned long n){
unsigned long result;
int max=0;
for(unsigned long m=n/2;m<=n;m++){
int count=0;
for(int i=2;i<=m/2;i++){
if(m%i==0){
count++;
}
}
if(count>max){
max=count ;
result=m;
}
count=0;
}
cout<<result<<"("<<max+2<<")"<<" <"<<1<<",";
for(int i=2;i<=result/2;i++){
if(result%i==0){
cout<<i<<",";
}
}
cout<<result<<"> "<<endl;
}
main(){
unsigned long n;
cin>>n;
Search(n);
system("pause");
}
18 楼
wlsss [专家分：150] 发布于 2006-08-19 12:11:00
/***********************************************
在N以内(小于等于N)找出一个数，要求：
1.这个数的约数的个数达到最大，
2.如果有好几个数满足条件1，仅取最小的那个数
***********************************************/
#include <stdio.h>
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[]);
int GetDivisor(unsigned long n); //得到n的约数个数
void main()
{
unsigned long n;
unsigned long *result;
int *count;
unsigned long arr[65535];
result = new unsigned long;
count = new int;
printf("输入范围(1~N):N=");
scanf("%ld",&n);
Search(n,result,count,arr);
printf("%ld\n%d\n%d",*result,*count,1);
for(int i=1;i<*count;i++)
{
printf(",%d",arr[i]);
}
printf("\n");
}
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[])
{
unsigned long i;
unsigned long num=1; //数
int divisor=1; //约数个数
int tmpdiv;
int k;
for(i=1;i<=n;i++)
{
tmpdiv=GetDivisor(i);
if(divisor<tmpdiv)
{
divisor=tmpdiv;
num=i;
}
}
*result=num;
*count=divisor;
k=0;
arr[k]=1;
for(i=2;i<=num;i++)
{
if(num%i==0)
arr[++k]=i;
}
}
int GetDivisor(unsigned long n)
{
unsigned long num=n;
unsigned long div[31]={0}; //质因数数组
int ddiv[31]={0};
int sum=1;
int i,k;
unsigned long j;
//以下获得质因数数组，比如n=360，则div={2,2,2,3,3,5}
for(i=0;;i++)
{
for(j=2;j<=num;j++)
{
if(num%j==0)
{
num=num/j;
break;
}
}
div[i]=j;
if(num==1) break;
}
//以下获得另外一个数组，保存各质因数的个数，比如
//div={2,2,2,3,3,5}，则ddiv={3,2,1}
i=0;
ddiv[0]=1;
for(k=1;k<=31;k++)
{
if(div[k]==div[k-1])
ddiv[i]++;
else if(div[k]!=0)
ddiv[++i]=1;
else break;
}
//得到因数的个数，如ddiv={3,2,1}，则sum=(3+1)(2+1)(1+1)
//因为如果num=(p1^n1)(p2^n2)(p3^n3)...
//其中p1,p2,p3...是质数，n1,n2,n3...是自然数
//则因数个数为(n1+1)(n2+1)(n3+1)...
for(i=0;i<=31;i++)
{
if(ddiv[i]==0) break;
sum*=(ddiv[i]+1);
}
return sum;
}
19 楼
coldgeek [专家分：0] 发布于 2006-08-19 13:13:00
好东西,不顶是罪恶
20 楼
abcdxjs [专家分：240] 发布于 2006-08-19 14:29:00
第一次正式参加.
这个题目还算容易,我以前写过类似的程序,求完全数的.
现在重新想来,原来以前的程序里面还有几个错误,现在完善了它,虽然速度下降了不少,但终于正确了.
//file: MostSubmultiple.c
//compiler: VC++ 6.0
#include "stdio.h"
#include "math.h"
#include "stdlib.h"
/*
基本思路: 搜索1 到 Num的平方根 范围内的约数,如果m是其约数,则 Num/m也是其约数
另外,由于求Num的平方根SquareBoot时sqrt函数是向下取整的,所以如果SquareBoot恰好
是Num的平方根,则只能算一个.如果不是而只是Num的一个约数,那么Num / SquareBoot也是
就多了两个约数
*/
//实际上,如果n大于2,则在n范围内约数个数最多的数中最小的一定是偶数,
//代码中屏蔽了处理奇数的部分,楼主如果觉得有奇特情况需要就把注释前后去掉
//数据类型采用unsigned long int
typedef unsigned long int ULI;
void Search(ULI n, ULI *pResult,ULI *pCount,ULI arr[]);
ULI Submultiple(ULI Num);//求出一个数的约数个数,这个函数实际上可以直接写在Search里面,这样效率更好
void Store(ULI Num, ULI TotalSubmultiple,ULI arr[]);//将符合条件的那个数的约数列举出来,存储在arr[]
#define MaxMemory 1000000
//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
void main()
{
ULI i, Count, Result;
ULI *pArr = NULL;
ULI n = 100000;
/*
for (i=2; i<=15; i++){
Count = Submultiple(i);
printf("%u 有 %u个约数 \n", i, Count);
}
*/
pArr = (ULI*)malloc(MaxMemory);//用来存放那个数的所有约数，按照从小到大的顺序
Search(n, &Result, &Count, pArr);
printf("%u以内约数最多且最小的数是 %u ,共有 %u 个约数,分别是: \n", n, Result, Count);
for (i = 0; i < Count; i++){
printf("%u ",*(pArr +i));
}
free(pArr);
pArr = NULL;
}
//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
void Search(ULI n, ULI *pResult,ULI *pCount,ULI arr[])
{
ULI i;
ULI MostSubmultiple = 1, Count;
ULI Result;
//for (i = 2; i <= n; i++){
//
//}
//实际上,如果n大于2,则在n范围内约数个数最多的数中最小的一定是偶数.
for (i = 2; i <= n; i += 2){
Count = Submultiple(i);
if (Count > MostSubmultiple){
MostSubmultiple = Count;
Result = i;
}
}
Store(Result, MostSubmultiple, arr);
*pResult = Result;
*pCount = MostSubmultiple;
}
//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
//求出一个数的约数个数
ULI Submultiple(ULI Num)
{
ULI Count;//约数的个数,最后要将1加入去
ULI i;
ULI SquareBoot = (ULI)sqrt(Num);//搜索到Num的平方根为止
Count = 0;
//if ( (Num & 1) == 0 ){//it's even 偶数
//搜索1 到 Num的平方根 范围内的约数,如果m是其约数,则 Num/m也是其约数
//所以将最后结果乘2,最后还要对Num % Mid进入讨论
for (i = 1; i < SquareBoot; i++){
//一个数除Num的余数,如果为0,则说明它是Num的约数
if (Num % i == 0) {Count++;}
}
//}
/*
else {//it's odd 奇数,只搜索小于Mid的奇数
for (i = 1; i < SquareBoot; i += 2){
if (Num % i == 0) {Count++;}
}
}
*/
Count <<= 1;//乘2
//如果Mid恰好真是Num的平方根(前面用sqrt函数是向下取整的)
if (SquareBoot * SquareBoot == Num){
Count++; //这里不能像前面一样乘2了,不然就多出了一个
}
else if (Num % SquareBoot == 0){//如果只是它的一个约数
Count += 2; //Num / Mid也是它的一个约数
}
return Count;
}
//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
//将符合条件的那个数的约数列举出来,存储在arr[]
//参数1: 符合条件的那个数 2.其约数的个数(以便定位) 3.要存储的数组地址
void Store(ULI Num, ULI TotalSubmultiple,ULI arr[])
{
ULI i, Count;
ULI SquareBoot = (ULI)sqrt(Num);//搜索到Num的平方根为止
Count = 0;
//从 arr[0]存储到 arr[--TotalSubmultiple]
for (i = 1; i < SquareBoot; i++){
//如果m是其约数,则 Num/m也是其约数
if (Num % i == 0) {
arr[Count++] = i;
arr[--TotalSubmultiple] = Num / i;
//由于这里实际上重复执行了两次 Num 除以 i,如果用汇编实现,效率更好!
}
}
//如果Mid恰好真是Num的平方根(前面用sqrt函数是向下取整的)
if (SquareBoot * SquareBoot == Num){
arr[Count++] = SquareBoot;
}
else if (Num % SquareBoot == 0){//如果只是它的一个约数
arr[Count++] = SquareBoot; //Num / Mid也是它的一个约数
arr[--TotalSubmultiple] = Num / SquareBoot;
}
}
//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
我来回复
您所在位置：