fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define endl '\n'
  4. #define task ""
  5. #define int ll
  6. using namespace std;
  7.  
  8. signed main()
  9. {
  10.     ios_base::sync_with_stdio(0);
  11.     cin.tie(0);
  12.     if (fopen(task".inp", "r"))
  13.     {
  14.         freopen(task".inp", "r", stdin);
  15.         freopen(task".out", "w", stdout);
  16.     }
  17.     int n, k; cin >> n >> k;
  18.     set <int> s;
  19.     for (int i = 1; i <= k; ++i)
  20.     {
  21.         int b; cin >> b; s.insert(b);
  22.     }
  23.     vector <int> a;
  24.     a.push_back(0);
  25.     for (auto i : s) a.push_back(i);
  26.     int q = a.size() - 1;
  27.     if (a[1] == 1)
  28.     {
  29.         cout << n; return 0;
  30.     }
  31.     vector <vector<int>> v (q + 1);
  32.     v[0].push_back(1);
  33.     for (int i = 1; i <= q; ++i)
  34.     {
  35.         for (int j = i; j >= 1; --j)
  36.             for(auto p : v[j - 1])
  37.                 if (p / __gcd(p, a[i]) * a[i] <= n) v[j].push_back(p / __gcd(p, a[i]) * a[i]);
  38.     }
  39.     int ans = 0;
  40.     for (int i = 1; i <= q; ++i)
  41.     {
  42.         for (auto p : v[i])
  43.         {
  44.             if (i & 1) ans += n / p;
  45.             else ans -= n / p;
  46.         }
  47.     }
  48.     cout << ans;
  49.     return 0;
  50. }
  51.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
30 3
2 3 5
stdout
copy 
22
https://ideone.com/67pEQD
language:
C++ (gcc 8.3)
created:
4 hours 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!