恩。。懒得编高精度了。。也没时间去AC了。。写个题解占个楼吧。。

先声明下，这只是个人看法，不代表标准做法（甚至这个做法都没有程序实现过。。）：

设读入k,则k=a1^p1*a2^p2...*an^pn，记s1=p1+p2+..+pn，那么最少按键次数就是a1+a2+..+an+2*s1。，则不同的按法总数则是这s1个质因数的排列，即s1!,由于第i个质因数重复pi次，故不同的按法总数s2=s1!/(p1!*p2!...*pn!)

先把通过率从4%降到了3%，再把通过率从3%升到4%，算是将功补过吧，嘿嘿！！！

我把“通过率”从3%加到了4%我把“通过”从6加到了7我把“提交”从184加到了190......

怎么分解啊

总算秒杀了 （加了个米勒拉宾优化）

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

PS:为什么我写了300行？？？？？？？？？？？？？？？？？？？？？？？？？？

Orz mike_nzk

这题太可怕了

这题可以不要高精。。

对于这种BT题，丢掉……

Flag 　　

题号 　　P1606

类型(?) 　　数论 / 数值

通过 　　2人

提交 　　144次

通过率 　　1%

难度 　　1

质因数分解``

虽然数据很大,但是我有一个很好的算法来求质因数——建立在miller-rabin算法上的，即使是10000000以上的数，也能秒杀！！！

以下是这种强大的质因数分解的程序，希望管理员别删，个人认为这个质因数分解相当强大，推荐一下

var

n:longint;

function gcd(a,b:longint):longint;

begin

if a=0 then gcd:=b

else gcd:=gcd(b mod a,a);

end;

function modular_exponentiation(a,b,n:longint):longint;

var

d,i,k:integer;

bb:array [0..1000] of 0..1;

begin

d:=1;

k:=-1;

while b>=2 do begin

inc(k);

bb[k]:=b mod 2;

b:=b div 2;

end;

inc(k);

bb[k]:=b;

for i:=k downto 0 do begin

d:=(d*d) mod n;

if bb[i]=1 then d:=(d*a) mod n;

end;

modular_exponentiation:=d;

end;

function miller_rabin(n,s:longint):boolean;

var

i,a:longint;

begin

randomize;

for i:=1 to s do begin

a:=random(n-1)+1;

if modular_exponentiation(a,n-1,n)1 then begin

miller_rabin:=false;

exit;

end;

end;

miller_rabin:=true;

end;

function pollard_rho(c,n:longint):longint;

var

i,x,y,k,d:longint;

begin

randomize;

i:=1;

x:=random(n);

y:=x;

k:=2;

repeat

inc(i);

d:=gcd(2*n+y-x,n);

if (d>1) and (d

先找出约数，然后枚举约数可以做到60分..下面给出ac算法..

算法基于这样一个结论：将读入的数A分解质因数以后，可行的操作是对于每一个质因数都执行操作A+C+V+V...（V的数量为质因数的数量），这样所有质因数的操作的乘积为答案,可以证明当质因数有2个2的时候，可以将原操作中两个2的操作变化成对4执行操作，有1个2和1个3的时候，操作可以变化成对6执行操作。

对于第一问，设读入的数为A，将A中2的幂和3的幂提取出来，设提取出来的数为c，设提取出来以后剩下的数为n，设N=p1^a1+p2^a2+...+pk^ak然后ans=sigama[ai*(pi+2)] +dp(c) dp(i)表示i对应的第一问的答案。

对于第二问，讨论：

对于任意数k,则k=a1^p1*a2^p2...*an^pn，记s1=p1+p2+..+pn，设f（k)=s1!/(p1!*p2!...*pn!) ，记d(k)=s1则：

若读入的A质因数分解后不含2 3，则f(A）为答案。

若读入的A质因数分解后不含2，含3，则f(A)为答案。

若读入的A质因数分解后含2不含3，则：

设2的幂次为k。

若k mod 2=0则答案等于f(A/2^k)*C(d(A/2^k)+k div 2,k div 2)

若k mod 2=1则答案等于f(A/2^(k-1))*C(d(A/2^(k-1))+k div 2,k div 2)+f(A/2^k)*C(d(A/2^k)+k div 2,k div 2)*k div 2

若读入的A质因数分解后含2且含3，则：

从0开始枚举4的幂，设枚举的4的幂为i，设A/4^i中6的幂为c，则ans=sigma(C(c+i,i)*f(A/4^i/6^c)*C(d(A/4^i/6^c)+c+i,c+i))

数据不是一般的大……

质因子分解~

但是初步研究表明~

因子为4、6时有特殊情况~

这么多人扯就没一个人过？？？》》。。。。。。

Flag 　　

题号 　　P1606

类型(?) 　　数论 / 数值

通过 　　0人

提交 　　51次

通过率 　　0%

难度 　　1

鉴于'伟大'的通过率通过 　　0人

提交 　　48次

通过率 　　0%

难度 　　1

此题XXXXXXX

沙茶题。

如果有人觉得数据有问题，可以发消息给我或者发讨论帖。（不过那么多人AC了，应该不会错了~）

PS:通过率上升是正常的，此题最后会在10%以上。

ORZ!

没救了。。。

沙茶题、、、一点也不沙茶

通过率 　　0% 通过率 　　0% 通过率 　　0% 通过率 　　0% 通过率 　　0%

ORZ!膜拜神牛宋文杰