35 条题解

  • 2
    @ 2016-08-27 20:59:17
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    int n,k,l,use[17],res[17];
    int num[1005];
    double min;
    bool flag;
    const int prim[17]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
    inline void dfs(int last,int now,int st,double sub)
    {
        if (sub>min) return;
        if (now==1){
            if (sub<min){
                min=sub;
                memcpy(res,use,sizeof(use));
            }
            return;
        }
        if (st>16) return;
        for (int i=l;i>=1;--i)
            if (now%num[i]==0)
                {
                    use[st]=num[i];
                    dfs(num[i],now/num[i],st+1,sub+log(prim[st])*(num[i]-1));
                    use[st]=0;
                }
    }
    inline bool isprime(int x){
        for (int i=2;i*i<=x;i++)
            if (x%i==0) return false;
        return true;
    }
    int main(){
        scanf("%d",&n);
        while (n--){
            scanf("%d",&k);
            min=1<<20;
            if (k==1){
                putchar('1');
                putchar('\n');
                continue;
            }
            if (isprime(k)){
                printf("2^%d\n",k-1);
                continue;
            }
            memset(num,0,sizeof(num));
           memset(res,0,sizeof(res));
            l=0;
            for (int i=2;i<=k-1;i++)
                if (k%i==0) num[++l]=i;
            dfs(k,k,1,1);
            flag=false;
            for (int i=1;i<=16;i++)
                if (res[i]!=0){
                    if (flag) putchar('*');
                    printf("%d",prim[i]);
                    if (res[i]>2) printf("^%d",res[i]-1);
                    flag=true;
                }
                putchar('\n');
        }
    }
    

    什么鬼题目。。

  • 0
    @ 2016-08-29 16:04:52

    var
    a:array[1..20]of longint=(2,3,5,7,11,13,17,19,23,29,31,37,39,41,43,47,51,53,57,59);
    b,d:array[1..30]of longint;
    k,n,i,j,lk:longint;
    maxz:real;
    procedure dfs(k,max,l:longint);
    var
    i,j:longint;
    c:real;
    begin
    if k=1 then
    begin
    c:=0;
    for i:=l-1 downto 1 do
    c:=c+(ln(a[l-i])/ln(10)*b[i]);
    if c<maxz then
    begin
    maxz:=c;
    d:=b;
    lk:=l;
    end;
    end;
    for i:=max to k do
    begin
    if k mod i=0 then
    begin
    b[l]:=i-1;
    dfs(k div i,i,l+1);
    end;
    end;
    end;
    begin
    readln(n);
    for i:=1 to n do
    begin
    maxz:=100000000000;
    readln(k);
    dfs(k,2,1);
    for j:=lk-1 downto 2 do
    begin
    write(a[lk-j]);
    if d[j]>1 then
    write('^',d[j],'*') else write('*');
    end;
    if d[1]>1 then
    writeln(a[lk-1],'^',d[1]) else writeln(a[lk-1]);
    end;
    end.

  • 0
    @ 2015-11-14 21:14:41

    1输出什么?

  • 0
    @ 2015-08-26 08:51:42

    我也错了0,2,9。

  • 0
    @ 2015-07-07 21:10:24

    和我一样错0,2,9三个点的各位,注意:k不一定要分解成质数!

    • @ 2016-08-27 21:05:55

      就这个原因我WA了好几次。。无语

  • 0
    @ 2013-08-06 20:24:16

    测试数据 #0: Accepted, time = 0 ms, mem = 824 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 824 KiB, score = 10

    测试数据 #2: Accepted, time = 0 ms, mem = 828 KiB, score = 10

    测试数据 #3: Accepted, time = 0 ms, mem = 828 KiB, score = 10

    测试数据 #4: Accepted, time = 15 ms, mem = 824 KiB, score = 10

    测试数据 #5: Accepted, time = 0 ms, mem = 824 KiB, score = 10

    测试数据 #6: Accepted, time = 62 ms, mem = 828 KiB, score = 10

    测试数据 #7: Accepted, time = 0 ms, mem = 820 KiB, score = 10

    测试数据 #8: Accepted, time = 0 ms, mem = 828 KiB, score = 10

    测试数据 #9: Accepted, time = 0 ms, mem = 824 KiB, score = 10

    Accepted, time = 77 ms, mem = 828 KiB, score = 100

    这个速度慢了吧
    我是求出约数从大到小
    然后DFS进行最优化剪枝

  • 0
    @ 2009-11-10 10:22:38

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    终于AC.....神奇的对数判断大小方法,OTL,OTZ,Orz!

  • 0
    @ 2009-11-06 17:03:38

    素数数组要开到12。。也就是最大37

  • 0
    @ 2009-11-03 13:07:28

    0分的人注意:

    一次幂不要输出“ ^1 ”

  • 0
    @ 2009-11-01 19:36:13

    以前一直认为这题太搞,没做

    今天难得来了兴致

    搜索方式换了好几次

    终于AC了

  • 0
    @ 2009-10-27 23:08:43

    数据已经无误。ORZ楼下众多神牛

  • 0
    @ 2009-09-30 23:03:07

    101个,赶不上最后一班车了……

    郁闷,调一个下午的程序一直不过。

    放学的时候再提交一下,竟然一样的程序再提交一遍就AC了?!

    我们可以把K分解成>=2的若干数

    K=k1*k2*k3*...*kn

    那么N=2^(k1-1)*3^(k2-1)*5^(k3-1)....第n个素数^(kn-1)

    递归分解K的所有情况,但是N可能会很大。

    我们就可以利用Ln(x)函数的单调递增的性质,而且有个好处就是

    ln(p^x)=x*ln(p) ln(a*b)=ln(a)+ln(b) 用实型保存即可。

    像ln(2^3*3^3*5^8)=3*ln(2)+3*ln(3)+8*ln(5)

    大大简化编程。

    还等什么?AC去吧。

  • 0
    @ 2009-09-21 17:10:52

    第100个。。高兴。。搜索题一般要很痛苦的想剪枝。。然后拼细心。。(MS更痛苦的是知道剪枝就是AC不了..)

    P.S.数据没问题了。。不用cheat.

  • 0
    @ 2009-09-19 16:05:24

    到底数据有没有问题啊,,,,,,,,,,,这道题让人真抓狂啊。。。。。。。。有问题就要改哇.......

  • 0
    @ 2009-08-22 16:59:39

    看了教主的题解,就如同在黑夜里看到了一颗闪亮的流星,如同在沙漠中连续几天没有喝水的人久旱逢甘霖那样,立刻瞬秒。。。

  • 0
    @ 2009-08-20 10:54:47

    可不可以对k进行分解质因数,然后爆搜+构造指数?

  • 0
    @ 2009-08-08 22:12:03

    暴搜指数..用对数存值

  • 0
    @ 2009-08-06 21:57:05

    好邪恶啊这题!

  • 0
    @ 2009-08-04 12:54:42

    这样的数据真是无语

    呵呵,错误的算法,竟然只错了需要CHEAT的两个点,真是无语

    我41856输出2^108*3^2*5*7*11*13*17*19*23

  • 0
    @ 2009-04-13 21:44:51

    数据好了

    AC了

信息

ID
1310
难度
7
分类
搜索 | 搜索与剪枝 点击显示
标签
(无)
递交数
438
已通过
80
通过率
18%
被复制
3
上传者