Description
对于任意输入的正整数n，请编程求出具有n个不同因子的最小正整数m。例如：n=4，则m=6，因为6有4个不同整数因子1，2，3，6；而且是最小的有4个因子的整数。
Input
n（1≤n≤50000）
Output
m
Sample Input
4
Sample Output
6
题解
高精度问题
如果不涉及加减法
可以对答案取对数进行计算
这是这题的小姿势
根据约数和公式
∏ i = 1 k ( a [ i ] + 1 ) prod_{i=1}^{k}{(a[i]+1)} i=1∏k(a[i]+1)
其中这个数N能被写成
p 1 a 1 p 2 a 2 . . . p_1^{a_1}p_2^{a_2}... p1a1p2a2...
设DP方程 f [ i ] [ j ] f[i][j] f[i][j]表示已经有i个约数，使用了前j个质数能组成的最小数
枚举最后一个质数的次数
显然有
f [ i ] [ j ] = ∑ m i n ( f [ i k ] [ j − 1 ] ∗ p r [ j ] k − 1 ) f[i][j]=sum min(f[frac{i}{k}][j-1]*pr[j]^{k-1}) f[i][j]=∑min(f[ki][j−1]∗pr[j]k−1)
然后 发现不能搞高精度DP
取对数
变成
f [ i ] [ j ] = ∑ m i n ( f [ i k ] [ j − 1 ] + ( k − 1 ) ∗ l o g ( p r [ j ] ) ) f[i][j]=sum min(f[frac{i}{k}][j-1]+(k-1)*log(pr[j])) f[i][j]=∑min(f[ki][j−1]+(k−1)∗log(pr[j]))
计算即可
因为N一定能被写成 ∏ i = 1 k ( a [ i ] + 1 ) prod_{i=1}^{k}{(a[i]+1)} ∏i=1k(a[i]+1)的形式
所以我们其实可以只预处理他的约数
状态改为 f [ i ] [ j ] f[i][j] f[i][j]表示到他的第i个约数，使用了前j个质数能组成的最小数
方程变为
f [ i ] [ j ] = ∑ p [ k ] ∣ p [ i ] f [ k ] [ j − 1 ] + ( p [ i ] p [ k ] − 1 ) ∗ l o g ( p r [ j ] ) f[i][j]=sum_{p[k]|p[i]}f[k][j-1]+(frac{p[i]}{p[k]}-1)*log(pr[j]) f[i][j]=p[k]∣p[i]∑f[k][j−1]+(p[k]p[i]−1)∗log(pr[j])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149/* : . : i i . i : . i . i . i : . i . i i : . . . . . . . .. . . . . . . . . . . . . : qQ . v2d . i: ..:ij.iBE .i EBj .irrivri.::iiiir7r. . SPd. : i UQB .BBBBE BBBQBBBBLiBB.1BBi :X: BBu . .KBBBBBBBBBBBBBBBQv :BBBBB . iBY PD. BBY vBBv. ..:gB1 rBM 7B1 RQP MBgvPPQBB uRq. .. . jBBQ.BBBr :.BBrQBBBBBL iQBB7:777gBSYvrKBBv:v71r..YPBBBBBBBBBBEBBB 7RBZQdBBBdEgBQE 1QBB1 QBBB: .:BBBBJ.qBBDBBBBBBBvrQBQBBBBBBBBBBBBBgg5UBBBBriiBQ1 rBB .:.:i. :KQBi ..:: :.. . . . ..... UBBB5 UJ: rBBBBXi . IQY i:.:.. YBs :BB IE. XBZ QBs 7BB rBBBBQBBBBBBBQBBBBq BQBBBBBBBBBBBBBBBBviBBE. .BBZ .BBgi. . BBBQSJ.Kb5BQgRBPv :5gQBBBQBB:YBvrBBd QBE BBdiBBBB5 .BB uBs iririiiriir7iii77i. ii .BBD . . uQ5Sv .BB::i::QBU BBQMBK. 7BBBP. DBq QB1 DQ7.L. sBBdQBBMBBBQBBBBBQDi BB5 . ...:BB KBJ uB1 UBBBL QBL RQb i:. BBPvi.UBBuY7v7iQBqrrur. BBE . :LBBBBBBJQBBBBQBBBJ :rvBBu:BBB1jBBPbBB SBBZIvSUguJXRBBB: 7QBB BBu .. BBQ r.XX... .QBIYXDJBB1 qBBBBi ir rMQBQ. .sPBBBBBBBBRBBD7 XBBi dB1. . .. .BBg i . . . . . .. ... . : i . . i i . i :r:. i . . vKKSj. . r .. :B: js . i . . rK .S: ::: r :v LS . ibi7gv . i :Ligi .QJ :g7 . . ...5d: . i2Sd rb. vj: . . .7:r27DBi . .Bb: . 7K..Ps uij1Pdr. ri . Sq :Kj7Ii . . :v: UvY: 7P. . . .7 .vIqX. .. . .dBRS7. . . qP . . . .. . . .. :r. .qi :2ZPi . . gs . .:K2 . .irvIs75K5XEKMKgZsD522YLri. iBB1i Pr .2r i iS: .isjjQ. .:rs5KPPMBBBZdBBgi:7Rd7XBBBRSMBBDZQZSr. rDYiiYdQSr. dY : Ys .iXbi. 7: 7v5gQZqPEKXUIjUIdbr ur jRQr1E: .rJgBBDL: iEv .sdD5Yi. MX . . i Si .vU57i .ibQBBgMPI175XUvsq5LBj :Li. jQLJ: . .rdBBQsYL :r1ISv: .gu . : .. iU r5Qu. :sBBD7qDqbbijPj5ISXv22UK .BY . .gSP: .q: rBBBBS . . .7KEYi. qv . . qBsY1i :IqBZqI2rUXLXQPrYjIuED2jZPv. KI . . .BR. rd .bBUBQu. . .isZK1: 5s : vPv. .idDBEP1XYKXQR1r5d2SdPqEDv7IEY Yv . KB.:U. :Ui .BJUBBB1 . rXqIrrB2 . v rQDM1dj7SM1qIuPgXJKS2sKU5urLDMr :Bi . .dBMi7BPYJ 1PKL: BjKIUPBB1 . . :irMX i . .vKDDr1YREIPgv1qS1Qbju1IS2US5vUZBu sr . :BBBBdXMDMgjv. : guJsP7rQgU: JdrsSv: 7 rQREJ5u2vuKv5dXKKPXqqXK1PSSqP2USqqBDj . 7QBQRPQriQg:..v7i:. MqEXBs72DQB: .iYYr..iPRJ 7 . .MRB221QqKrYSSXdXXuBZuSguL1sPMDQQDPPgBi . :RBBMB5 PELBBBj vP. irRBgRPEv .Ju7ivv7vLi. . : 7DQUdSPqgIqUsKSYv5Si2PrruJSBZR5r:: :Z: .irvX::qPPZMBBQgs .Xs LPuXBBi :Dd2rLsr. . i YBZ7Lg2bUPLb172Xr7PQvJuuuMBbX7. .uRu. :QEBQRRBZgggQBSrY. :SQQX :27:. . i .EP2PX1qJYIPuu5I2g2uB5YXbDZPJ .rr. . 7gZU7r7vYvvvJqBQRBMdgDMgBQQr r5BBr .gB2LgEsPPuKE2IrM5Iu1U2JXgS. :7vvvsYLL7. .rs77JJr. JBQDBbdEZBRgBP . .YIUvirvBQ: . XQQSqgDJ7qg5bPXqLd1bQ2JQB2. ..:7Lv7: iBQSREEBQQRBP: iSPL7. rBu QgUjEE2qJbKsjX2duqYKr5BS. .. .rYr. dBQBZBQBKgM. . rZ2: jEi vJdPIJI5UPSYKb5uLbLSDEu . :BBgBPEBr . .... . iBK. YvLb7K5L7ubsjgJuuSsPQ7 .....:iiirr77v7vrv1PXU77rr::. :E. . .. .. sgi LuKQrsSd5XQPqSij7bBu :ivu5J7i::::::::::i::.::iri.. :Ei. ..i715qLPdUqS. iBi . 7UPBv2IPqP1IdXLZZPr . . .sY .ir:. .. .QE .. UsJRubSv7ggUJr1Qg: .. r5 vd. d5YPrSqX7QIvPRBX. . . ..:i777r7vJvr: . .rZ . .iE5rr 2LKXj2E17DjSMSQi ..ii7uqS522J7:..... .. 7Z. . .75Y::. 7KdBZEXXBQ: r7PQqdEjJEPJuZJ iIPK1j7:.:. .:i:...... :P .iLuvPSsXQbr .JBP sLPP1uqs2XR7JQ: .:i. .:71ZBBBQEDDMbdMBBBdui: rZ. . bB. UUqK7vSIv5PuDg .YdQBBBBQBMESJ777s1bPdEgRQBBRUi. .5 . .gq vLZPvvbKLdSIBv . 1MBRQBBBMEbZPvgBRJrLY7Uj2J7rvPDQBBgUY722 ... .. iBJ irIKvUPI7M1SRi . . 7BB1JUvSd1Y512IYSBMKLPv1XirsivvUKgDgBBBBBBKr:. .. uE. D2KIJ5D17EPdd. . qBJv.ivivYi7JvrLrLEgbbP1PE:71sS5sDq7vDQD2qbgBBBMJi rR7 vJPbvJq2YgEQ2 .BP.L7ijIEuiivr7vii1PKgg5dRjXgUSujJ7JgJ7Piru1UKMBBQM2i .2I:. vrXP1Xg2vJjbL . . sBBuXI1gBgE2SI7vIrrsIiSISdBSEZ1bggQv7Es:U77YLirugggDBBBgKUJrri:.:7IEP. XU1UubPuLu7LY . :5RBgUBBPPdggBEUdqIKXviuJrYdPPq2PKKBqY1jrj75I1LL7UXZBBdPEQBP7jIIdKSBB. . sIDbX5X5KRBSE .ZXLXI7q57UJ5IRUUZP5KZguivSv1S55bS12BMBjJ7dXBgZIqr7dqMEPBEQQ: KB7 ... .. PU7v5MPJ7KZPD iBbU7v77:r7irYdIud5KqZPsrs2vYUsJuPP5SLKgQdEEgdPgMX7qvI5DXbMX :BQ 511sSdZXI51vg. . LgXgU77iir5dddBMMBBBP5dP52S2gBQ2vL22RdBQBPQP15SdMR1Jivrr:MBr SBv .jDBMbuv: .. vU52sujjUEq1E. . . 2MrBDU5PQBZP7.:..irDQQPdBBRqi. .:jXQMBPrIjXXBP1iuii.BE .BX rSQK:...i1dX7. KJ1svuqsrEgPK . v1rDQDBj:. .LQBS. .JBE.r7555RbbK55PBr . Kg 7QM. 7BBv PXdEu5PsLKv5di 7E1dKi :J. :gg1iq1LsQRRYuBP .r KQi iBg .2Q5. . IjPP1ID5UJYdBY rBBS . . :BErj7YU5ZPdBZ vBv :Rd IBi 2UKK7JPXuIgQBb . bBi . . . . EBPYv7srIKBB vBr sBi . .B1 vvbb15d5bSPLPB: . rB: .. . :qBKQvYLJRK iQ2 :ZBBr . Rv . SY57vDIKZLuuKBi .BB. . . . bBXgudD5v .2BBgqqbgBJ . ... .E5 v75vYqPPq5KPjJE: . iBBr . .BMvBQEv: BBq1EsSQS5Bi . . :BL vUUs7YuJrXJd7:BP . .PQqv: .. .:77juBQJsi rBQYiJU1JX5PRb: vBL . dZsY55RS1qjdqrBBL .JPMRP77. .:.....:.:i7vjuSqEEbXqqquL7. . .jBQJvdR5vuuuJ5BBq: isBB . . BQ7v1KDu5qYSqsJgQ: .r7IEPUs11uj25X21JJri::... 7QB1rPQY2duIQKXZJ7BBdu7:isDZ5: .. LYRgsvSUPqX1UUI2Bd. ii2MEgI7dRSJ1sSBX7SPXsPZBBXr77. vBB1PBZMQggZDZMXgBBDgMRbbEQQRZPZRPKSPbDRBDKujsuYv25Ys2qSEPDMMddZgZMQBBBgQBQEPsqXJSqsIP52M5UPPsvERZi s5QgPQBIDMMDgDgDgBBgEBBBBBBQQBBBBQBBBBBQQBBBBBBBBQBBBBBQBBBBBBBBBQBBBBBBBMBQgESDDSEKUPgU2qSqUrPBBv. . rrPBBgMDMQRRMQgQDMQBQBMgRQggDgRBBBgZgBBBQBBBBBBBBBBBBBS: ..vbBBBQBQMbSQQMEYSuLI5uPKv1D77PBBXi ... i LdMdKKqqPgZSgd1PZPSLXPXSZZXPZIQZJ5EKdDgMMdqYr.::.:bB: LBXIQBKPgBquP2PZuUuUSXj5ZqXBB7 i:BP2j:vYs7q5sZI:2uvv7Ss7UYKs51r51rJLjDg7: .BvPPgX1vrii:2Qi vBbIMQuZrsDP55uu2XYdBQU: . rPBLJ27PXu7SP2QIvSJsPKgYPPisXq1Lg51ZBdr 2Q: .. .qBU.:vbv. :IQBqiSs2KYLudKv7QQb. BBXr7P1PXXsPSjD5757YPPE1JJiXPZj7sSQK: 1v iBu g7 . iDBPQsIPuIP7vZB1. . MuiK7uKKj11Pj:S1UbuJXv2JJSKKLU2rSgX .....:::...::.: .Bd..i.:bj .SB7 .:: KBgMv1gu2KqDBZ: .:ii:ri::iiirrrviii7i. */ #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; const int pr[17]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}; double f[550][20],Log[550]; int p[550],plen,n; int A[1100000],len; void mul(int x) { for(int i=1;i<=len;i++)A[i]*=x; for(int i=1;i<len;i++)A[i+1]+=A[i]/10,A[i]%=10; while(A[len]>=10) { A[len+1]+=A[len]/10;A[len]%=10; len++; } } int main() { Log[1]=0; for(int i=2;i<=60;i++)Log[i]=Log[i>>1]+1; scanf("%d",&n); //n=(k1+1)(k2+1)(k3+1)... for(int i=1;i<=n;i++)if(!(n%i))p[++plen]=i; for(int i=1;i<=16;i++)Log[i]=log(pr[i]); for(int i=1;i<=16;i++)f[0][i]=0; for(int i=2;i<=plen;i++)//枚举约数 { for(int j=0;j<=16;j++)f[i][j]=1e9; for(int j=1;j<i;j++)if(!(p[i]%p[j])) { int t=p[i]/p[j];//这个质数贡献t-1次幂 for(int k=1;k<=16;k++)f[i][k]=min(f[i][k],f[j][k-1]+(t-1)*Log[k]); } } A[1]=1;len=1; int pa=0,gg=0; for(int i=1;i<=16;i++)if(f[plen][i]<f[plen][pa]||!pa)pa=i; for(int i=plen,nxt;i!=1;i=nxt,pa--) { for(nxt=1;p[i]%p[nxt]||f[i][pa]<f[nxt][pa-1]+(p[i]/p[nxt]-1)*Log[pa]-1e-5;nxt++); for(int k=1;k<p[i]/p[nxt];k++) mul(pr[pa]); } for(int i=len;i>=1;i--)printf("%d",A[i]); puts(""); return 0; }
最后
以上就是还单身冬日最近收集整理的关于[bzoj1225][DP][奇技淫巧]求正整数的全部内容，更多相关[bzoj1225][DP][奇技淫巧]求正整数内容请搜索靠谱客的其他文章。
![[bzoj1225][DP][奇技淫巧]求正整数](/uploads/reation/bcimg8.png)
发表评论 取消回复