fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. int lcm0(int a, int b){
  5.         return (a*b)/(__gcd(a, b));
  6. }
  7. signed main(void){
  8.         ios::sync_with_stdio(0); cin.tie(NULL);
  9.         int n, k;
  10.         cin >> n >> k;
  11.         int ans = 0;
  12.         vector<int> V(k);
  13.  
  14.         for(int i = 0; i < k; i++) cin >> V[i];
  15.  
  16.         for(int i = 1; i < (1 << k); i++){
  17.                 int lcm = -1;
  18.                 int bits = 0;
  19.                 for(int j = 0; j <= k; j++){
  20.                         if(i&(1 << j)){
  21.                                 if(lcm == -1){
  22.                                         lcm = V[j];
  23.                                 }
  24.                                 else{
  25.                                         lcm = lcm0(lcm, V[j]);
  26.                                 }
  27.                                 bits++;
  28.                         }
  29.                 }
  30.                 if(bits%2){
  31.                         int add = (n-1)/lcm + 1;
  32.                         ans += add;
  33.                 }
  34.                 else{
  35.                         int add = (n-1)/lcm + 1;
  36.                         ans -= add;
  37.                 }
  38.         }
  39.         cout << n - ans << '\n';
  40. }
Time limit exceeded #stdin #stdout 5s 1054208KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/LRNN6x
language:
C++14 (gcc 8.3)
created:
7 years 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!