fork(1) download
copy 
  1. // #usr/bin/sunny-karira/
  2. //Golden Sword in the game
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long Int;
  8.  
  9. const int N(100), M(300000);
  10. Int dp[N][M], k;
  11. int n, a[N];
  12.  
  13. Int get(int n, Int k) {
  14. 	if (n == -1)
  15. 		return 1;
  16. 	if (k < M) {
  17. 		if (dp[n][k] != -1)
  18. 			return dp[n][k];
  19. 		return dp[n][k] = k / a[n] + get(n - 1, k) - get(n - 1, k / a[n]);
  20. 	}
  21. 	return k / a[n] - get(n - 1, k / a[n]) + get(n - 1, k);
  22. }
  23.  
  24. int main() {
  25. 	//freopen("ans13.txt", "r", stdin);
  26.     //freopen("write13.txt","w",stdout);
  27. 	cin >> k >> n;
  28. 	for (int i = 0; i < n; i++)
  29. 		cin >> a[i];
  30. 	sort(a, a + n);
  31. 	memset(dp, -1, sizeof dp);
  32. 	cout << k - get(n - 1, k);
  33. 	return 0;
  34. }
Success #stdin #stdout 0.16s 237056KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/Ak5jj4
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 years ago
visibility:
secret

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!