F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 3552 >> 卡log^5n/512
GXZlegend @ 2017-12-04 09:59:30
[ Quote ] [ Edit ] [ Delete ] 1#
所以还是老老实实的写正解吧。。。
mcfx @ 2017-12-04 12:11:06
[ Quote ] [ Edit ] [ Delete ] 2#
T=int(raw_input())
for I in range(T):
n=int(raw_input());t=n;a=0;b=0;c=1;d=[1,1,2,1,4,4,4,3,4,1]
while t>0:t/=2;a+=t
while n>0:c=c*d[n%10]%5;n/=5;b+=n
a=a-b+1
if a>1:a=0
t=3
while b>0:
if b&1:c=c*t%5
t=t*t%5
b/=2
print (a*5+c*6)%10
GXZlegend @ 2017-12-04 14:13:48
[ Quote ] [ Edit ] [ Delete ] 3#
等等我的复杂度分析好像有点问题。。。
大概是O(log^3n/8) 。。。
反正就是核心代码长成下面那样的都过不去:
for(i = a ; i.len ; i = i / 2) a2 = a2 + i / 2;
for(i = a ; i.len ; i = i / 5) a5 = a5 + i / 5;
for(i = a ; i.len ; i = i / 2)
{
for(j = i ; j.len ; j = j / 5)
{
a3 = a3 + j / 10 + data(j[0] % 10 >= 3);
a7 = a7 + j / 10 + data(j[0] % 10 >= 7);
a9 = a9 + j / 10 + data(j[0] % 10 >= 9);
}
}
[Top] [Previous Page] [Next Page]

HOME Back