?? divi.cpp
字號:
#include <stdio.h>
#include <memory.h>
#include <math.h>
#define Maxint 31623
int prime[Maxint+1];
int n_prime,best;
int calc_prime(int n) //用篩法求出在n范圍內的素數列表
{
int i,j;
bool isprime[Maxint+1];
memset(isprime,0,sizeof(isprime));
if(n>Maxint) n=Maxint;
for(i=2; i*i<=n; i++)
{
if(!isprime[i])
for(j=i+i; j<=n; j+=i)
isprime[j]=1;
}
j=0;
for(i=2; i<=n; i++)
if(isprime[i]==0)
prime[j++]=i;
return j;
}
//枚舉質數,在給定的數據范圍內搜索構成一個number,滿足div(number)最大
void find(int total, int down, int up, int number, int start)
//total當前的約束個數,down、up上下界,number由當前這total個約束構成的值,start起始的素數
{
if(number>=1 && total>best)
best=total;
if(down==up && down>number)
if(total*2>best) best=total*2;
for(int i=start; i<n_prime; i++)
{
if(prime[i]>up) return ;
else {
int k=prime[i],t=total,low=down-1,high=up,num=number;
while(true) {
t+=total;
low/=k;
high/=k;
if(low==high) break; //在當前數據范圍內,f所能達到的最大的
num*=k;
find(t,low+1,high,num,i+1);
}
//t*logk(up)<best 假設當前上界最多可以被分解為k的個數為p,
//而p個若都是不同素數的話,構成的個數為p=2^p最大,
//根據乘法原理,那么t*p<test說明繼續往下做沒有意義,可以剪枝
int p=int(log(up)/log(k));
p=1<<p;
if(total*p<best) return;
}
}
}
void swap(int &a, int &b)
{
int temp;
temp=a;
a=b;
b=temp;
}
int main()
{
int s,f;
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d%d",&s,&f);
if(s>f) swap(s,f);
n_prime=calc_prime(f);
if(s==1&&f==1)
best=1;
else
{
best=2;
find(1,s,f,1,0);
}
printf("%d\n",best);
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -