almost 4 years ago

被虐了一下午之后滚过来写题解T_T
huzecong大神讲的灰常好……所以就贴过来了
【之前的图搞不过来了……原网址懒得去找……就附一下之前的blog地址好了】
http://lavender1010.blog.com/2014/06/23/%E3%80%90bzoj1225%E3%80%91%E3%80%90hn2001%E3%80%91%E6%B1%82%E6%AD%A3%E6%95%B4%E6%95%B0/
注意的思想:
1、分解质因数求因子数的方法
2、为了不用高精度常数大转化为log
3、搜索加隐含的剪枝会比dp快
【总之现在应该是懂了……】

/**************************************************************
    Problem: 1225
    User: LaVenDer
    Language: C++
    Result: Accepted
    Time:32 ms
    Memory:820 kb
****************************************************************/

#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define Mod 10000
using namespace std;
int prime[50]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int n;
double minn=125678927890.0;
double Log[50]={0.0};
int result[50]={0},temp[50]={0};
int ans[101]={0};
void cheng(int x)
{
    int i,temp=0;
    for (i=1;i<=ans[0];i++)
    {
        ans[i]=ans[i]*x+temp;
        temp=ans[i]/Mod;
        ans[i]%=Mod;
    }
    ans[ans[0]+1]=temp;
    while (ans[ans[0]+1])
    {
        ++ans[0];temp=ans[ans[0]]/Mod;ans[ans[0]]%=Mod;
    }
}
void search(int step,int a,int b,double num)
{
    if (num>minn) return;
    if (a==1)
    {
        if (num<minn)
        {
            minn=num;result[0]=step-1;
            for (int i=1;i<=step-1;i++) result[i]=temp[i];
        }
        return;
    }
    for (int i=1;i*i<=a&&i<=b;i++)
        if (a%i==0)
        {
            if (i!=1)
            {
                temp[step]=i-1;
                search(step+1,a/i,i,num+Log[step]*(i-1));
            }
            temp[step]=a/i-1;
            search(step+1,i,a/i,num+Log[step]*(a/i-1));
        }
}
int main()
{
    scanf("%d",&n);
    int i;
    for (i=1;i<=25;i++) Log[i]=log(prime[i])/(double)log(2);
    search(1,n,n,0.0);
    ans[0]=ans[1]=1;
    for (i=1;i<=result[0];i++)
      for (;result[i];result[i]--)
        cheng(prime[i]);
    printf("%d",ans[ans[0]]);
    for (i=ans[0]-1;i>=1;i--) printf("%04d",ans[i]);
    printf("\n");
}
← 【bzoj2539】【KM】丘比特的烦恼 【bzoj1491】【noi2007】社交网络 →
 
comments powered by Disqus