fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define  int long long
  4. #define  all(v) v.begin(),v.end()
  5. using namespace std;
  6. #define ll long long
  7.  
  8. const int N = 1e6 + 10;
  9. ll p5[20];
  10. ll suf[20];
  11. ll fact[20];
  12. ll calc(int n, int k) {
  13.     return fact[n - k + 1] / fact[k];
  14. }
  15. ll answ(ll n) {
  16.     if (n == 0) return 0;
  17.     ll sumd = 0;
  18.     vector<int> d;
  19.     ll val = n;
  20.     while (val > 0) {
  21.         d.emplace_back(val % 5);
  22.         sumd = sumd + val % 5;
  23.         val /= 5;
  24.     }
  25.     reverse(d.begin(), d.end());
  26.     int sz = d.size();
  27.     ll pre = 0;
  28.     for (int i = 0; i < sz; i++) {
  29.         for (int j = 0; j < d[i]; j++) {
  30.             sumd = sumd + (pre + j) * p5[sz - 1 - i] + suf[sz - 1 - i];
  31.         }
  32.         pre += d[i];
  33.     }
  34.     return (n * (n + 1) / 2 - sumd) / 4;
  35. }
  36.  
  37. void sol() {
  38.     ll l, r;
  39.     cin >> l >> r;
  40.     cout << answ(r) - answ(l - 1) << endl;
  41. }
  42.  
  43. signed main() {
  44.  
  45.     int t = 1;
  46.     cin >> t;
  47.     p5[0] = 1;
  48.     for (int i = 1; i < 18; i++) {
  49.         p5[i] = p5[i - 1] * 5;
  50.     }
  51.     fact[0] = 1;
  52.     for(int i = 1; i <= 17; i++){
  53.         fact[i] = fact[i - 1] * i;
  54.     }
  55.     for (int ss = 1; ss <= 17; ss++) {
  56.         for (int j = 0; j < 5; j++) {
  57.             for (int k = 1; k <= ss; k++) {
  58.                 suf[ss] = suf[ss] + calc(ss, k) * j;
  59.             }
  60.         }
  61.     }
  62.     ll sumd = 0;
  63.     vector<int> d;
  64.     ll val = 255;
  65.     while (val > 0) {
  66.         d.emplace_back(val % 5);
  67.         sumd = sumd + val % 5;
  68.         val /= 5;
  69.     }
  70.     reverse(d.begin(), d.end());
  71.     int sz = d.size();
  72.     ll pre = 0;
  73.     for (int i = 0; i < sz; i++) {
  74.         for (int j = 0; j < d[i]; j++) {
  75.             sumd = sumd + (pre + j) * p5[sz - 1 - i] + suf[sz - 1 - i];
  76.         }
  77.         pre += d[i];
  78.     }
  79.     cout<<sumd<<endl;
  80.     ll dd = 0;
  81.     for(int i = 0; i<= 255; i++){
  82.         ll val = i;
  83.         while(val > 0){
  84.             dd = dd + val % 5;
  85.             val/=5;
  86.         }
  87.     }
  88.     cout<<dd<<endl;
  89.     while (t--) {
  90.         sol();
  91.     }
  92.  
  93. }
  94.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
288
1648
556941322274924002
https://ideone.com/18Zos9
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!