35 条题解

• @ 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');
}
}
``````

什么鬼题目。。

• @ 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
for i:=1 to n do
begin
maxz:=100000000000;
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.

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

1输出什么?

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

我也错了0,2,9。

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

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

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

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

• @ 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进行最优化剪枝

• @ 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!

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

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

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

0分的人注意：

一次幂不要输出“ ^1 ”

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

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

今天难得来了兴致

搜索方式换了好几次

终于ＡＣ了

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

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

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

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

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

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

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

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

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

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

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

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

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

暴搜指数..用对数存值

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

好邪恶啊这题！

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

这样的数据真是无语

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

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

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

数据好了

AC了

ID
1310

7

(无)

438

80

18%

3