0ms怎么做的,打表?
by skydogli @ 2019-04-30 14:34:05
@[skydogli](/space/show?uid=7480) 本质上是打表吧。。
by zl_just @ 2019-04-30 17:01:33
~~终于放学了~~
真正的$O(logn)$算法
```cpp
#include<cstdio>
long long ans;
const int p = 5;
const int sp=(p*(p-1))>>1;
int main() {
int n;
scanf("%d",&n);
int base1=p,base=1;
for(register int s=n/p;s;s/=p) {
int base2=base1*p,x=(n+1)/base2;
long long a=sp*x*base1;
int y=(n+1)%base2,z=y/base1;
a+=((z*(z-1))>>1)*base1;
a+=(y%base1)*(y/base1);
base1=base2;
ans+=a*base; base=p*base+1;
}
printf("%lld\n",ans);
return 0;
}
```
之前的是$O(p*logn)$
虽然$p$是$5$
by zl_just @ 2019-04-30 17:29:51
@[zl_just](/user/125925) 我的logn的做法只用10行
by critnos @ 2020-03-03 11:07:37
@[mcyl35](/user/203623) 时隔一年的回复(笑哭
by zl_just @ 2021-06-12 22:09:32
~~捞一手远古帖子~~
by zhangcheng001 @ 2021-08-28 17:28:40