HDU 4133 StrangeStandard 타 표?

Problem Address：http://acm.hdu.edu.cn/showproblem.php?pid=4133
【머리말】
문 제 를 풀 자마자 시 계 를 칠 수 있 을 거 라 고 생각 했다.
상한 선 은 20 억 이지 만 진짜 good number 는 많 지 않 을 것 같 습 니 다.
그 러 자 와르르 폭력 적 으로 시 계 를 치기 시작 했다.
근 데 곧 안 되 겠 더 라 고요.
폭력 타 표 는 안 나 올 거 야.
그리고 소수 로 칠 수 있다 고 생각 했 어 요.
근 데 20 억 소수?
인터넷 에서 신마 1 억 이내 의 소수 3 초 안에 나 온 코드 를 찾 았 는데 256 MB 메모리 의 기 계 를 도망 쳐 죽 였 다.
어찌 할 수 없다.
어젯밤 부터 규칙 을 찾기 시작 했다.울퉁불퉁 한 길 을 걸어오다.
결국 천천히 모색 해 냈 다.
시계 타 는 사람 을 냈 다.15ms。
그리고 시계 없 는 걸 로 냈어요.15ms 입 니 다.
아무래도 데이터 가 약 한 것 같 습 니 다.
[사고방식]
우선 소수 에 따라 이 소수 들 이 구성 할 수 있 는 같은 약수 의 최소 수 를 찾 아 보 자.
까다 로 운 말.
우선 어떤 수 를 확정 하 는 것 은 틀림없이 소수 로 구 성 된 것 이다.
그리고 모든 소 수 를 매 거 하 는 동시에 같은 소수 의 다른 개 수 를 매 거 하여 20 억 이하 의 수 를 계산한다.
이와 동시에 그것 의 약수 개 수 를 계산 해 냈 다.
만약 소수 와 그 개 수 를 이미 알 고 있다 면,대략 몇 개 수 는 구하 기 어렵 지 않 을 것 이다.
예 를 들 어 특정한 숫자 에 포 함 된 질 인 자 는 Pi 이 고 해당 하 는 질 인자 의 개 수 는 Qi 이다.그러면 약 몇 개의 수 는(Q1+1)*(Q2+1)*...*(Qn+1)이다.
그리고 같은 약수 에 대해 최소 치 를 기록한다.
마지막 으로 얻 은 조 수 는 작은 것 부터 큰 것 까지 대응 하 는 최소 수 이다.
그리고 이 배열 을 다시 한 번 스 캔 해서 앞 보다 작은 숫자 를 빼 세 요.
결국 20 억 원 이내 의 모든 good number 를 얻 었 습 니 다.
그리고 입력 한 숫자 마다 good number 에서 2 점 을 찾 으 면 됩 니 다.
이 문 제 는 위의 그런 연산 에 따라 배열 을 얻어 시 계 를 치 거나 시 계 를 치지 않 고 직접 계산 해도 된다.
문 제 는 정말 모든 소 수 를 매 거 한다 면 결 과 를 낼 수 없 을 것 이다.
관찰 을 통 해 약 몇 개의 수가 일정 하 다 면 틀림없이 소수 곱 하기 로 얻 은 수가 더 작 을 것 이다.
그래서 작은 범위 내의 질 수만 있 으 면 요 구 를 만족 시 킬 수 있다 는 것 을 알 수 있다.
여기 서 는 최소 8 개 만 있 으 면 20 억 이내 의 good number 를 만족 시 킬 수 있다.
이 여덟 개의 질 수 는 prime[]에 저장 되 어 있다.
동시에 필요 한 최대 개 수 를 미리 기록 하여 ct[]에 저장 할 수 있 습 니 다.
【코드】
비 타 표

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int getdiv(int n)//     
{
	if (n==1) return 1;
	int i;
	int s = 2;
	int m = (int)sqrt((double)n);
	for (i=1; i<=m; i++)
	{
		if (n%i==0) s+=2;
	}
	if (m*m==n) s--;
	return s;
}

const __int64 maxn = 2000000000;

vector<__int64>v, vt;

__int64 prime[8] = {2, 3, 5, 7, 11, 13, 17, 19};
int ct[8] = {31, 20, 14, 12, 9, 9, 8, 8};

map<int, __int64>hash;//          
map<int, __int64>::iterator it;

void dfs(int x, int n, int k, __int64 s)
{
	if (x==n) return;
	int i;
	__int64 t = s;
	for (i=1; i<ct[x]; i++)
	{
		t *= prime[x];
		if (t<=maxn)
		{
			if (hash.find(k*(i+1))==hash.end()) hash[k*(i+1)] = t;
			else if (t<hash[k*(i+1)]) hash[k*(i+1)] = t;
			dfs(x+1, n, k*(i+1), t);
		}
		else break;
	}
}

bool cmp(const __int64 &a, const __int64 &b)
{
	return a<b;
}

void init()
{
	hash.clear();
	hash[1] = 1;
	dfs(0, 8, 1, (__int64)1);
	v.clear();
	int i,j;
	for (it=hash.begin(); it!=hash.end(); it++)
		v.push_back((*it).second);
	sort(v.begin(), v.end(), cmp);
	vt.clear();
	vt.push_back(1);
	for (i=1; i<v.size(); i++) vt.push_back(getdiv(v[i]));
	for (i=1,j=0; i<vt.size(); i++)
	{
		if (vt[i]>vt[j])
		{
			j++;
			vt[j] = vt[i];
			v[j] = v[i];
		}
	}
}

__int64 bs(int s, int t, __int64 x)
{
	int left, right, mid;
	__int64 ans;
	left = s-1;
	right = t;
	while(left<=right)
	{
		mid = (left+right)>>1;
		if (x>=v[mid])
		{
			ans = v[mid];
			left = mid+1;
		}
		else right = mid-1;
	}
	return ans;
}

int main()
{
	int t, i;
	__int64 n;
	init();
	scanf("%d", &t);
	for (i=1; i<=t; i++)
	{
		scanf("%I64d", &n);
		printf("Case #%d: %I64d
", i, bs(0, 67, n));
	}
	return 0;
}

시 계 를 치다

#include <iostream>
using namespace std;

__int64 v[70] = {1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,
15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,
554400,665280,720720,1081080,1441440,2162160,2882880,3603600,4324320,6486480,7207200,8648640,
10810800,14414400,17297280,21621600,32432400,36756720,43243200,61261200,73513440,110270160,
122522400,147026880,183783600,245044800,294053760,367567200,551350800,698377680,735134400,
1102701600,1396755360};

__int64 bs(int s, int t, __int64 x)
{
    int left, right, mid;
    __int64 ans;
    left = s-1;
    right = t;
    while(left<=right)
    {
        mid = (left+right)>>1;
        if (x>=v[mid])
        {
            ans = v[mid];
            left = mid+1;
        }
        else right = mid-1;
    }
    return ans;
}

int main()
{
    int t,i;
    __int64 n;
    scanf("%d", &t);
    for (i=1; i<=t; i++)
    {
        scanf("%I64d", &n);
        printf("Case #%d: %I64d
", i, bs(0, 67, n));
    }
    return 0;
}