fork download
copy 
  1. //                                                           .=*#=
  2. //                                                        .=*=+* -#:
  3. //                                                      -*+. +=   .#=
  4. //                                                    -*=   *-     .#=
  5. //                                                  :*=    *#++#*   .%:
  6. //                                                 ++.    *-  =+     -#
  7. //                                               :*-     *-  *=       %-
  8. // .------::.                                   -*.     +=   -+++-.   *#
  9. // -*:-=+*#%#*++-.                             =+      -+        :+*- +@.
  10. // :*      .-++-:=++:                         ++      .#          .*: +%-
  11. // .#        .:+#- .=*=.                     =+       *:        :++.  *+=
  12. //  %       -%*=-=*.  :*+.                  -*       :*      :++=.    #-+
  13. //  #:       .=*- .*:   :*=         .:==++++*        +-     -**+:    :*:+
  14. //  +=         -#:  *-    :*-   :=++=-:.             =*-   :+++-     *-:+
  15. //  -#      .=*-     *-     =*+*=:                     -*= ==       .# -#++++++++=-:
  16. //   @:    =*:        #:     ..                          -*-#       *: ==        .:-+++:
  17. //   **   :#:         .#.                                 .*@.     =+  +:             .-*+:
  18. //   :@:   .=++=:.     -*                                   +.    :#   #.                .+*:
  19. //    ##       :-*@*   +-                                        .#.  .#                   .++=-.
  20. //    :@+       =#*++-.#                                         *:   -+                      .-+++-
  21. //     *%-           #+-                                              *.                          .-*+.
  22. //     .##-          +@                                           -. .#                              .++.
  23. //      :*++         :%                                  .=+.     :*:*:                                :*-
  24. //       =+-*:        -                                :++.        .**                    =.             +=
  25. //        =+.++:                                     .++.            #.                   ==              +=
  26. //         =+ .=*=.                                 .*:              *:                   *:               *:
  27. //          -*.  :++=:                             .#.               #.                .-*-                .#
  28. //           :*:    .=:                            *:               +=   .-=+++++==++++=:                   *:
  29. //            .*=               ...                .               += -++=:.                                :+
  30. //              -*:   ..    =++++==++++=:                        :*+++-                                      #
  31. //               .++. ==    .          .==                     .+%*=.                                        %
  32. //                 .*+==                                      =#%=                                           %
  33. //                   :#*                         .:.        -***..::.                                        %
  34. //                     #:                      +%@@:      -*-+%++=--*-                                      .#
  35. //                     .*-                     :=*=     -*- =%-     *:                                      -=
  36. //                       =*=.                         =*-  -*       # .-.                                   #.
  37. //                         :=#*++++++++++++++++-:::-+*-    #.      .*+=#.                                  ==
  38. //                           *:   .*-         #----:      ==           %+++++++++:                        -*
  39. //                           %    -*+-       .#:          #.                    +-                       -*
  40. //                           %      ##:+**. =*%.         -%                    -+                       ++
  41. //                           *:     #:+: :**-+=         .##                   :*                      :*-
  42. //                           :#=- +-#      :*:         .#:#                  :#.                    :*+.
  43. //                            .*#+*+.     :*.         .*: %                 .#*+=:                :*+.
  44. //                                        #..+       :*:  #.                    .++            :+*-
  45. //                                        :**=  #  :++.   ==                   .*+.       .:=++=.
  46. //                                          :=++*++=.     .#                   .+%+==++++++-.
  47. //                                                         *:           .-+++++=-::..
  48. //                                                         :*       .=++=:.
  49. //                                                          +-    -*+:
  50. //                                                          .#..=*-
  51. //                                                           =#*:
  52. //                                                           .-
  53.  
  54. #include <bits/stdc++.h>
  55. #define prob ""
  56. #define int long long
  57. using namespace std;
  58. void file(){
  59.     freopen(prob".INP", "r", stdin);
  60.     freopen(prob".OUT", "w", stdout);
  61. }
  62. void Init() {
  63.     ios_base::sync_with_stdio(false);
  64.     cin.tie(nullptr);
  65.     cout.tie(nullptr);
  66.     //file();
  67. }
  68. const int maxn = 200002;
  69. struct Query {
  70.     int d, id, type;
  71. };
  72. int n, q;
  73. int a[maxn + 7];
  74. long long ans[maxn + 7];
  75. vector<int> b[maxn + 7];
  76. vector<Query> Q[maxn + 7];
  77. int c[maxn + 7], pf[maxn + 7];
  78. void sieve() {
  79.     for (int i = 1; i <= maxn; ++i) {
  80.         for (int j = i; j <= maxn; j += i) {
  81.             b[j].push_back(i);
  82.         }
  83.     }
  84. }
  85. void Sol() {
  86.     sieve();
  87.     cin >> n >> q;
  88.     for (int i = 1; i <= n; ++i) {
  89.         cin >> a[i];
  90.     }
  91.     for (int i = 1; i <= q; ++i) {
  92.         int l, r, d;
  93.         cin >> l >> r >> d;
  94.         Q[r].push_back({d, i, 1});
  95.         Q[l - 1].push_back({d, i, -1});
  96.     }
  97.     for (int i = 0; i <= n; ++i) {
  98.         if (i > 0) {
  99.             for (int x : b[a[i]]) {
  100.                 c[x]++;
  101.             }
  102.             pf[a[i]]++;
  103.         }
  104.         for(auto &ev : Q[i]) {
  105.             int t = c[ev.d];
  106.             for(int x : b[ev.d]) {
  107.                 if(x < ev.d) {
  108.                     t += pf[x];
  109.                 }
  110.             }
  111.             ans[ev.id] += ev.type * t;
  112.         }
  113.     }
  114.     for (int i = 1; i <= q; ++i) {
  115.         cout << ans[i] << " ";
  116.     }
  117. }
  118. signed main(){
  119.     Init();
  120.     Sol();
  121.     return 0;
  122. }
  123.  
  124.  
Success #stdin #stdout 0.15s 42152KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XmPQAr
language:
C++ (gcc 8.3)
created:
2 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!