fast O(polylog n) time algorithm, C++ 0ms 100%
An algorithmic math problem.\nFirst 5 digits: numerical analysis.\nLast 5 digits: number theory.\n\n#define double long double\nconst double PI=atan((double)1)*
An algorithmic math problem.\nFirst 5 digits: numerical analysis.\nLast 5 digits: number theory.\n```\n#define double long double\nconst double PI=atan((double)1)*4,E=exp((double)1),\n  B[]={1,1./2,1./6,0,-1./30,0,1./42,0,-1./30,0,5./66,0,-691./2730,0,7./6,0,-3617./510,0,43867./798,0,-174611./330};\nconst int M=10;\ndouble log_fac(double n){\n\tdouble ans=n*log(n/E)+log(n)/2+log(sqrt(PI*2));\n\tfor (int i=2;i<=M;++i)ans+=pow(-1,i)*B[i]/(i*(i-1)*pow(n,i-1));\n\tif (n<20){\n\t\tans=0;\n\t\tfor (int i=1;i<=n;++i)ans+=log(i);\n\t}\n\treturn ans;\n}\nint leading(int l,int r){\n\tdouble t=log_fac(r)-log_fac(l-1);\n\tt/=log((double)10); t-=int(t)-4;\n\treturn pow(10,t);\n}\n\nconst int P=3125;\ntemplate<class T> T extend_gcd(T a,T b,T &x,T &y){\n\tif (!b){x=1;y=0;return a;}\n\tT res=extend_gcd(b,a%b,y,x); y-=x*(a/b);\n\treturn res;\n}\ntemplate<class T>\ninline T inv(T a,T M){\n\tT x,y; extend_gcd(a,M,x,y);\n\treturn (x%M+M)%M;\n}\nconst int inv2=inv(2,P);\nint exp(int x,int y,int z){\n\tint ans=1;\n\twhile (y){\n\t\tif (y&1)ans=ans*x%z;\n\t\tx=x*x%z;y>>=1;\n\t}\n\treturn ans;\n}\nint Chinese_Remainder_Theorem(int A[],int M[],int n){\n\tfor (int i=1;i<n;++i){\n\t\tint x,y,P=M[0]*M[i];\n\t\textend_gcd(M[0],M[i],x,y);\n\t\tx=(x*(A[i]-A[0])%P+P)%P;\n\t\tA[0]=(x*M[0]+A[0])%P; M[0]=P;\n\t}\n\treturn A[0];\n}\n// PolynomialMod[Product[If[Mod[i,5]>0,5^4*x+i,1],{i,1,5^4}],3125]\nint calc(int x,int d){\n\tswitch(d){\n\t\tcase 0: return x%5?x%P:1;\n\t\tcase 1: return (24+250*x+875*x%P*x+1250*x%P*x%P*x+625*x%P*x%P*x%P*x)%P;\n\t\tcase 2: return 124;\n\t\tcase 3: return 624;\n\t\tcase 4:\n\t\tcase 5: return 3124;\n\t}\n\treturn 0;\n}\nint get(int l,int r,int d){\n\tif (l>r||d<0)return 1;\n\tint mod=pow(5,d),l0=(l-1)/mod+1,r0=(r+1)/mod,res=1;\n\tfor (int i=l0;i<r0;++i)res=res*calc(i,d)%P;\n\tif (l0<r0)return res*get(l,l0*mod-1,d-1)%P*get(r0*mod,r,d-1)%P;\n\telse return get(l,r,d-1);\n}\nstring abbreviateProduct1(int left, int right) {  // brute force\n    long long suff = 1, c = 0, total = 0, max_suff = 100000000000LL;\n    double pref = 1.0;\n    for (int i = left; i <= right; ++i) {\n        pref *= i;\n        suff *= i;\n        while (pref >= 100000) {\n            pref /= 10;\n            total = total == 0 ? 6 : total + 1; \n        }\n        while (suff % 10 == 0) {\n            suff /= 10;\n            ++c;\n        }\n        suff %= max_suff;\n    }\n    string s = to_string(suff);\n    return to_string((int)pref) + (total - c <= 10 ? "" : "...") \n    \t+ (total - c < 5 ? "" : s.substr(s.size() - min(5LL, total - c - 5))) + "e" + to_string(c);\n}\nclass Solution {\npublic:\n\tstring abbreviateProduct(int l, int r) {\n\t\tif (r-l<20)return abbreviateProduct1(l,r);\n\t\tint last=1,l0=l,r0=r,zeros=0;\n\t\twhile (l0<=r0){\n\t\t\tlast=last*get(l0,r0,5)%P;\n\t\t\tl0=(l0-1)/5+1; r0/=5;\n\t\t\tzeros+=r0-l0+1;\n\t\t}\n\t\tlast=last*exp(inv2,zeros,P)%P;\n\t\tint A[]={0,last},M[]={32,3125};\n\t\tlast=Chinese_Remainder_Theorem(A,M,2);\n\t\tchar str1[15]; sprintf(str1,"%05d",last);\n\t\treturn to_string(leading(l,r))+"..."+string(str1)+"e"+to_string(zeros);\n\t}\n};\n```
['Math']