#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');
    }
}

什么鬼题目。。

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.

1输出什么?

我也错了0,2,9。

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

测试数据 #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进行最优化剪枝

编译通过...

├ 测试数据 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!

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

0分的人注意：

一次幂不要输出“ ^1 ”

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

今天难得来了兴致

搜索方式换了好几次

终于ＡＣ了

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

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去吧。

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

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

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

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

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

暴搜指数..用对数存值

好邪恶啊这题！

这样的数据真是无语

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

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

数据好了

AC了