fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. vector<int> computeMobius(int maxN) {
  7.     vector<int> mu(maxN + 1, 1);
  8.     vector<int> spf(maxN + 1, 0);
  9.     for(int i = 2; i <= maxN; ++i){
  10.         if(spf[i] == 0){
  11.             spf[i] = i;
  12.             for(int j = i * i; j <= maxN; j += i){
  13.                 if(spf[j] == 0){
  14.                     spf[j] = i;
  15.                 }
  16.             }
  17.         }
  18.     }
  19.     for(int i = 2; i <= maxN; ++i){
  20.         if(spf[i/spf[i]] == spf[i]){
  21.             mu[i] = 0;
  22.         }
  23.         else{
  24.             mu[i] = -mu[i/spf[i]];
  25.         }
  26.     }
  27.     return mu;
  28. }
  29.  
  30. ll countSquareFree(ll N, const vector<int> &mu) {
  31.     ll limit = sqrt(N);
  32.     ll res = 0;
  33.     for(ll k = 1; k <= limit; ++k){
  34.         res += (ll)mu[k] * (N / (k * k));
  35.     }
  36.     return res;
  37. }
  38.  
  39. int main(){
  40.     ios::sync_with_stdio(false);
  41.     cin.tie(0);
  42.     int T = 1;
  43.     // cin >> T;
  44.     int maxK = 31623;
  45.     vector<int> mu = computeMobius(maxK);
  46.     while(T--){
  47.         ll l, r;
  48.         cin >> l >> r;
  49.         ll sf_r = countSquareFree(r, mu);
  50.         ll sf_l_minus_1 = (l > 1) ? countSquareFree(l - 1, mu) : 0;
  51.         ll answer = sf_r - sf_l_minus_1;
  52.         if(l <=1 && r >=1){
  53.             answer -=1;
  54.         }
  55.         cout << answer << "\n";
  56.     }
  57. }
Success #stdin #stdout 0s 5264KB
comments (?)
stdin
copy 
1 100000
stdout
copy 
60793
https://ideone.com/easfFX
language:
C++14 (gcc 8.3)
created:
12 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!