1914.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1914 on 2005-12-08 at 15:05:39 */ 
#include <cstdio>
#include <string>

const int MAX = 128;
const int DIV_MAX = 10;
const int prime[DIV_MAX] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
const int LIMIT = 2000000000;

int main()
{
	long long n, anti[MAX], total[MAX];
	int divn[MAX][DIV_MAX];
	int k = 0, i, j;
	int divi, divj;
	
	memset(divn, 0, sizeof(divn));
	anti[0] = total[0] = 1;
	while(anti[k] < LIMIT) {
		anti[k+1] = LIMIT+1;
		for(i = 0; i <= k; i++) {
			for(j = 0; j < DIV_MAX; j++) {
				long long div = total[i] * (divn[i][j] + 2) / (divn[i][j] + 1);
				if(div > total[k] && anti[i]*prime[j] < anti[k+1]) {
					anti[k+1] = anti[i] * prime[j];
					total[k+1] = div;
					divi = i;
					divj = j;
				}
			}
		}
		k++;
		for(i = 0; i < 10; i++) {
			divn[k][i] = divn[divi][i];
		}
		divn[k][divj]++;
	}
	while(scanf("%lld", &n) != EOF) {
		for(i = k; i >= 0; i--) {
			if(anti[i] <= n) {
				printf("%d\n", anti[i]);
				break;
			}
		}
	}
	
	return 0;
}