主题:第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个回复)
31 楼
幸运的小猫 [专家分:0] 发布于 2006-08-19 23:25:00
main()
{int a=2,b=5;
printf("a=%%d,b=%%d\n".a.b);}这个两个%%是什么意思〉能告诉我吗?谢谢
32 楼
seekmm [专家分:380] 发布于 2006-08-19 23:46:00
嘿嘿,我也来一次!
#include <stdio.h>
#include <stdlib.h>
int arr[100],count,result,n;
void Search(unsigned long n)
{int i,j,t,k;
for(i=1;i<=n;i++)
{t=0;
for(j=1;j<i;j++)
{if(i%j==0)
t++;
}
if(t>count)
{count=t;t=0;result=i;
for(j=1;j<=i;j++)
{if(i%j==0)
arr[t++]=j;
}
}
}
for(k=0;k<t;k++)
printf("%d,",arr[k]);
}
int main()
{
printf("Please Enter n:");
scanf("%d",&n);
Search(n);
printf("\nn=%d,result=%d\n",n,result);
system("PAUSE");
}
33 楼
lilike123 [专家分:0] 发布于 2006-08-20 00:00:00
不错,不错,非常的不错!
34 楼
BigCarrot [专家分:10] 发布于 2006-08-20 00:11:00
第一次路过这里,看上去这个题目比较有意思
就做了一个试试看
不是很动这里的规矩
不知道我得代码是否符合标准
// t9.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdio.h"
unsigned int primearr[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
const int primenum = 12;
unsigned __int64 maxN = 0xFFFFFFFF;
struct node
{
unsigned int number;
int count;
char prime;
char two;
struct node* next;
};
struct node *head = 0;
struct node resultarray[4000];
int totalnum = 0;
void adjust(node *p)
{
node *q = p->next;
while (q && (q->count <= p->count))
{
p->next = q->next;
delete q;
q = p->next;
}
}
void enqueue(node *p)
{
node *q = head;
node *last = q;
if (head == 0)
{
head = p;
p->next = 0;
return;
}
if ((p->number < head->number) ||
((p->number == head->number) && (p->count > head->count)))
{
p->next = head;
head = p;
adjust(head);
return;
}
while (q && (p->number > q->number))
{
if (p->count <= q->count)
{
delete p;
return;
}
last = q;
q = q->next;
}
if (q && (p->number == q->number) && (p->count <= q->count))
{
delete p;
return;
}
last->next = p;
p->next = q;
adjust(p);
}
void buildresult()
{
node *p;
node *n1;
node *n2;
head = new node;
head->next = 0;
head->number = 2;
head->count = 2;
head->prime = 0;
head->two = 1;
while (head)
{
unsigned __int64 num1, num2, res;
resultarray[totalnum] = *head;
totalnum++;
p = head;
head = p->next;
n1 = new node;
n1->two = p->two;
n1->prime = p->prime + 1;
num1 = p->number;
num2 = primearr[n1->prime];
res = num1 * num2;
if (res <= maxN)
{
n1->number = (unsigned int)res;
n1->count = p->count * 2;
enqueue(n1);
}
n2 = new node;
n2->two = p->two + 1;
n2->prime = p->prime;
num1 = p->number;
res = num1 * 2;
if (res <= maxN)
{
n2->number = (unsigned int)res;
n2->count = (n2->two + 1) * p->count / (p->two + 1);
enqueue(n2);
}
delete p;
}
}
int c = 0;
void getnextvalue(int index, int primenum, int value, unsigned long arr[])
{
if (primenum > resultarray[index].prime)
{
arr[c] = value;
c++;
return;
}
getnextvalue(index, primenum+1, value, arr);
getnextvalue(index, primenum+1, value * primearr[primenum], arr);
}
void generatearray(int index, unsigned long arr[])
{
unsigned int x = 1;
c = 0;
for (int i=0; i<= resultarray[index].two; i++)
{
getnextvalue(index, 1, x, arr);
x = x * 2;
}
}
void sortarr(int count, unsigned long arr[])
{
unsigned long tmp;
int index;
for (int i=0; i<count-1; i++)
{
index = i;
for (int j=i+1; j<count; j++)
if (arr[j] < arr[index])
index = j;
if (index != i)
{
tmp = arr[i];
arr[i] = arr[index];
arr[index] = tmp;
}
}
}
35 楼
BigCarrot [专家分:10] 发布于 2006-08-20 00:12:00
代码太长了
一贴不让发
所以只好发了两铁
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[])
{
int i=0;
if (totalnum == 0)
buildresult();
while ((i < totalnum) && (n > resultarray[i].number)) i++;
if (i == totalnum)
i--;
if (n < resultarray[i].number)
i--;
*result = resultarray[i].number;
*count = resultarray[i].count;
generatearray(i, arr);
sortarr(*count, arr);
}
int main(int argc, char* argv[])
{
unsigned long n, result;
int count;
unsigned long arr[4000];
n = 0xffffffff;
Search(n, &result, &count, arr);
printf("result=%u \tcount=%d\n", result, count);
for (int i=0; i<count; i++)
printf("%u\t", arr[i]);
return 0;
}
36 楼
wshong [专家分:1880] 发布于 2006-08-20 01:30:00
#include<math.h>
#include<stdio.h>
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[])
{
unsigned long x=0;
int m,a,max=0;
unsigned long i,j,k=0;
if(n>=60)
{ a=60;
}
else if(n>=6) {
a=6;
}
else
{a=1;
}
m=n%a;
for(i=n-m;i>n/2;)
{
int count1=0;
for(j=1;j<=(unsigned long)sqrt(i);j++)
{
if(i%j==0)
count1++;
}
if(i==(unsigned long)sqrt(i)*(unsigned long)sqrt(i))
count1=2*count1-1;
else count1=2*count1;
if(count1>=max)
{
max=count1;//最大
x=i;//result
}
i=i-a;
}
for(j=1;j<=(unsigned long)sqrt(x);j++)
{
if(x%j==0)
{ arr[k]=j;k++;
}
}
if(max%2==0)
{
for(i=k,j=k-1;i<max;i++,j--)
{
arr[i]=x/arr[j];
}
}
else{
for(i=k,j=k-2;i<max;i++,j--)
{
arr[i]=x/arr[j];
}
}
*result=x;
*count=max;
}
void main()
{
unsigned long n,result;
int count,i;
unsigned long arr[1000];
scanf("%d",&n);
Search(n,&result,&count,arr);
printf("result:%d count:%d\narr[%d]:",result,count,count);
for(i=0;i<count;i++)
printf("%d ",arr[i]);
}
呵呵~我的算法数太大的时候很慢,想不出什么办法了
37 楼
mantiser [专家分:300] 发布于 2006-08-20 01:35:00
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define assert(con) if(!(con)){printf("Argument NULL\n");return;}
#define MAX 100
void Search
(
unsigned long n, /*输入*/
unsigned long *result, /*最大约数的整数*/
int *count, /*最大约数个数*/
unsigned long arr[] /*存放约数*/
);
void Search
(
unsigned long n, /*输入*/
unsigned long *result, /*最大约数的整数*/
int *count, /*最大约数个数*/
unsigned long arr[] /*存放约数*/
)
{
unsigned long temp = n;
int iMaxCount = 0;
unsigned long iResult = 0;
unsigned long i,j;
unsigned long alTemp[100] = {0};
int k;
assert((result != NULL) &&
(count != NULL) &&
(arr != NULL));
*count = 0;
*result = 0;
for(i=1;i<n;i++)
{
if(iMaxCount > *count)
{
*count = iMaxCount; /*保存最大约数个数*/
*result = iResult; /*保存最大约数*/
memcpy(arr,
alTemp,
iMaxCount * sizeof(long));/*保存约数*/
}
iMaxCount = 0;
k = 0;
memset(alTemp, 0, MAX);
//printf("[%d]:",i);
/*求i的约数个数*/
for(j=1;j<=i;j++)
{
if(i%j)
{
continue; /*不是约数*/
}
else
{
iMaxCount++; /*约数加一*/
alTemp[k++] = j;/*保存约数*/
iResult = i; /*保存约数个数最大的值*/
//printf(" %d ",j);
}
}
//printf("\n");
}
printf("[%d]:",*result);
for(k=0;k<*count;k++)
{
printf(" %d ",arr[k]);
}
printf("\n");
}
int main ()
{
/*printf("Call afun():%d\n",afun(80));*/
unsigned long arr[100] = {0};
unsigned long n = 100;
unsigned long result;
int count;
Search(n,&result, &count, arr);/*测试*/
}
38 楼
iAkiak [专家分:8460] 发布于 2006-08-20 02:21:00
#pragma warning(disable: 4786)
#include <cstdio>
#include <cmath>
#include <cassert>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
class PrimeList
{
public:
typedef vector<unsigned long>::size_type size_t;
unsigned long get(size_t index)
{
if (index >= d.size())
generate(index);
return d[index];
}
void generate(size_t index)
{
if (d.size() == 0)
{
unsigned long buf[] = {2, 3, 5, 7, };
d.insert(d.begin(), buf, buf + sizeof(buf)/sizeof(buf[0]));
}
for (unsigned long p = d.back() + 2; d.size() <= index; p += 2)
{
if (isPrime(p))
d.push_back(p);
}
}
bool isPrime(unsigned long n)
{
size_t i;
unsigned long dd;
for (i = 0; dd = get(i), dd * dd <= n; i++)
{
if (n % dd == 0)
return false;
}
return true;
}
vector<unsigned long> d;
} gPrimeList;
struct node
{
node():value(0),count(0){}
unsigned long value;
unsigned long count;
map<unsigned long, unsigned> p;
struct cmp
{
bool operator () (const node *a, const node *b)
{
if (a->count == b->count)
return a->value > b->value;
return a->count < b->count;
}
};
};
// greedy
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[])
{
node max_n;
max_n.value = 1;
max_n.count = 1;
for(;;)
{
node max_n2, t;
for (PrimeList::size_t i = 0;; i++)
{
__int64 p = gPrimeList.get(i);
if (p > 0x10000Lu || p * p > __int64(n))
break;
__int64 value = __int64(max_n.value) * p;
if (value > __int64(n))
break;
t.value = unsigned long(value);
t.p = max_n.p;
unsigned count = ++t.p[i];
t.count = max_n.count / count * (count + 1);
if (node::cmp()(&max_n2, &t))
{
max_n2 = t;
}
}
if (node::cmp()(&max_n, &max_n2))
{
max_n = max_n2;
}
else
break;
}
//printf("%d %d %d %d\n", max_n.value, max_n.count, gPrimeList.d.size(), gPrimeList.get(gPrimeList.d.size() - 1));
*result = max_n.value;
*count = max_n.count;
n = max_n.value;
int i, j = 0;
for (i = 1; i * i <= n; i++)
{
if (n % i == 0)
{
arr[j++] = i;
arr[*count - j] = n / i;
}
}
}
39 楼
jackin0627 [专家分:1270] 发布于 2006-08-20 02:54:00
////Vc++6.0
#include "string.h"
#include "math.h"
int Count(int num[],int len)//求带权值的序列的组合数(权值表示此位置可以取多少个不同的值)
{
int i,sum=1;
for(i=0;i<len;i++)
{
sum*=num[i]+1;
}
return sum;
}
unsigned long fac[32];
int num[32];
int factor(unsigned long n)//求n的所求素数因子放入fac[!max][]中,并将此因子出现次数放入num[]中,返回因子个数
{
unsigned long f;
int i,c=0;
for(f=2;f<=n;f++)
{
if(n%f==0)
{
for(i=0;i<c;i++)
{
if(f==fac[i])
{
num[i]++;
break;
}
}
if(i>=c)
{
fac[c]=f;
num[c]=1;
c++;
}
n=n/f;
f=1;
}
}
return c;
}
int parr=0;
void getarr(unsigned long arr[],unsigned long fac[],int num[],int len,int cur,unsigned long val)
{
unsigned long v;
if(len==cur+1)
{
for(int i=0;i<=num[cur];i++)
{
arr[parr++]=val*(unsigned long)pow(fac[cur],i);
}
}
else
{
for(int i=0;i<=num[cur];i++)
{
v=val* (unsigned long)pow((double)fac[cur],(double)i);
getarr(arr,fac,num,len,cur+1,v);
}
}
}
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[])
{
unsigned long i,j,e,cur,t;
int max=0,ml,c,l;
unsigned long mfac[32];
int mnum[32];
if(n<=0)
{
*result=0;
*count=0;
return;
}else if(n==1)
{
*result=1;
*count=1;
arr[0]=1;
return;
}
e=n/2;
for(i=n;i>e;i--)
{
l=factor(i);
c=Count(num,l);
if(c>max)
{
memcpy(mfac,fac,l*sizeof(unsigned long));
memcpy(mnum,num,l*sizeof(unsigned long));
max=c;
cur=i;
ml=l;
}
else if(c==max&&i<cur)
{
memcpy(mfac,fac,l*sizeof(unsigned long));
memcpy(mnum,num,l*sizeof(unsigned long));
max=c;
cur=i;
ml=l;
}
}
// printf("%ld,%d\n",cur,max);
// for(i=0;i<ml;i++)
// printf("[%d:%ld]",mnum[i],mfac[i]);
// printf("\n");
parr=0;
getarr(arr,mfac,mnum,ml,0,1);
for(i=0;i<max-1;i++)
for(j=i+1;j<max;j++)
if(arr[i]>arr[j])
{
t=arr[i];
arr[i]=arr[j];
arr[j]=t;
}
// for(i=0;i<max;i++)
// {
// printf("{%ld}",arr[i]);
// }
*result=cur;
*count=max;
}
40 楼
wlsss [专家分:150] 发布于 2006-08-20 04:58:00
//在18楼已经提交过一个程序,但是计算速度太慢。
//以下把18楼的程序改进了一下,基本思想没变。
//Visual C++ 6.0下编译通过。
/***********************************************
在N以内(小于等于N)找出一个数,要求:
1.这个数的约数的个数达到最大,
2.如果有好几个数满足条件1,仅取最小的那个数
***********************************************/
#include <stdio.h>
#include <math.h>
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[]);
void main()
{
unsigned long n;
unsigned long *result;
int *count;
unsigned long arr[65535]={0};
result = new unsigned long;
count = new int;
printf("输入范围(1~N):N=");
scanf("%ld",&n);
Search(n,result,count,arr);
printf("约数最多数是:%ld,它的约数的个数是:%d\n",*result,*count);
printf("它的约数分别为:");
for(int i=0;i<*count;i++)
{
if(i%8==0)
printf("\n");
printf("%9d",arr[i]);
}
printf("\n");
}
void Search(unsigned long n, unsigned long *result,int *count,unsigned long arr[])
{
unsigned long *prime;
int pnum=(int)sqrt(n);
unsigned long rtl=1;
int cnt=1;
unsigned long i;
int k;
int a,b,c;
prime=new unsigned long[pnum];
/*** 得到1~sqrt(n)的质数数组,存到prime[]中***/
prime[0]=2;
a=1;
for(b=3;b<=pnum;b++)
{
for(c=0;c<a;c++)
{
if(prime[c]>sqrt(b))
{
prime[a++]=b;
break;
}
if(b%prime[c]==0)
break;
}
}
prime[a]=0;
pnum=a;
/*****************************************/
for(i=1;i<=n;i++)
{
/******以下得到i的约数的个数,存到tmpcnt中**************/
unsigned long num=i;
unsigned long primediv[31]={0}; //质因数数组
int divnum[31]={0};
int tmpcnt=1;
int j,l,m;
//以下获得质因数数组,比如n=360,则primediv={2,2,2,3,3,5}
for(l=0;;l++)
{
for(j=0;j<pnum;j++)
{
if(num%prime[j]==0)
{
num=num/prime[j];
break;
}
}
if(j==pnum)
{
primediv[l]=num;
num=1;
}
else
primediv[l]=prime[j];
if(num==1) break;
}
//以下获得另外一个数组,保存各质因数的个数,比如
//primediv={2,2,2,3,3,5},则divnum={3,2,1}
l=0;
divnum[0]=1;
for(m=1;m<=31;m++)
{
if(primediv[m]==primediv[m-1])
divnum[l]++;
else if(primediv[m]!=0)
divnum[++l]=1;
else break;
}
//得到因数的个数,如divnum={3,2,1},则tmpcnt=(3+1)(2+1)(1+1)
//因为如果rtl=(p1^n1)(p2^n2)(p3^n3)...
//其中p1,p2,p3...是质数,n1,n2,n3...是自然数
//则因数个数为(n1+1)(n2+1)(n3+1)...
for(l=0;l<=31;l++)
{
if(divnum[l]==0) break;
tmpcnt*=(divnum[l]+1);
}
/**********************************************/
if(cnt<tmpcnt)
{
cnt=tmpcnt;
rtl=i;
}
}
*result=rtl;
*count=cnt;
k=0;
arr[k]=1;
arr[cnt-1]=rtl;
for(i=2;i<=sqrt(rtl);i++)
{
if(rtl%i==0)
{
arr[++k]=i;
arr[cnt-k-1]=rtl/arr[k];
}
}
}
我来回复