• Source 
    1. #include <stdio.h>
    2. #include <math.h>
    3. #include <stdint.h>
    4. #include <inttypes.h>
    5.  
    6. #pragma GCC optimize "O4"
    7.  
    8. #define TSIZE 1000
    9. // 900+1 at least
    10. int64_t itab[TSIZE];
    11. int64_t ritab[TSIZE];
    12. int smax;
    13.  
    14. const double WRATIO=6.5;
    15.  
    16. int numof2x5y(int64_t x)
    17. {
    18.   int s=0;
    19.   for ( ; x>0; x/=5 )
    20.     s+=64-__builtin_clzll(x);
    21.   return s;
    22. }
    23.  
    24. void init(int64_t n)
    25. {
    26.   smax=numof2x5y(n);
    27.   itab[1]=1;
    28.   ritab[1]=n;
    29.   for ( int s=2; s<=smax; s++ )
    30.   {
    31.     int64_t d=itab[s-1];
    32.     int64_t u=n;
    33.     while ( u-d>1 ) {
    34.       int64_t c=(u+d)/2;
    35.       int r=numof2x5y(c);
    36.       if ( r<s )
    37.         d=c;
    38.       else
    39.         u=c;
    40.     }
    41.     itab[s]=u;
    42.     ritab[s]=n/u;
    43.   }
    44. }
    45.  
    46. __attribute__((always_inline))
    47. inline int64_t phi(int64_t t)
    48. {
    49. //  return t-t/2-t/5+t/10;
    50.   return (t+1)/2-(t+5)/10;
    51. }
    52.  
    53. int64_t f(int64_t n)
    54. {
    55.   int64_t a=0;
    56.   init(n);
    57.   int64_t gborder=sqrt(n*WRATIO);
    58.   int sborder;
    59.   for ( sborder=smax; ritab[sborder]<gborder; sborder-- );
    60.  
    61.   const int giv[4]={1,3,7,9};
    62.   for ( int i=0; i<4; i++ )
    63.   {
    64.     int64_t g=giv[i];
    65.     for ( int s=smax; s>=sborder; s-- )
    66.       for ( ; g<=ritab[s]; g+=10 )
    67.         a+=s*(n/g);
    68.   }
    69.  
    70.   int64_t q=1,phiu=phi(n),phid=phi(n/2);
    71.   for ( int s=1; s<sborder; s++ )
    72.     for ( ; q<itab[s+1]; q++,phiu=phid,phid=phi(n/(q+1)) )
    73.       a+=q*s*(phiu-phid);
    74.  
    75.   return a;
    76. }
    77.  
    78. int main(void)
    79. {
    80.   int64_t n;
    81.   scanf("%"SCNd64,&n);
    82.   printf("%"PRId64"\n",f(n));
    83. }