fork(1) download
copy 
  1. #include <vector>
  2. #include <iostream>
  3. #include <algorithm>
  4. using namespace std;
  5. long long n; int m, a[24]; vector<long long> v;
  6. vector<long long> unique(vector<long long> u) {
  7. 	vector<long long> ret;
  8. 	if(u.size() >= 1) ret.push_back(u[0]);
  9. 	for(int i = 1; i < u.size(); i++) {
  10. 		if(u[i - 1] != u[i]) ret.push_back(u[i]);
  11. 	}
  12. 	return ret;
  13. }
  14. int main() {
  15. 	scanf("%lld%d", &n, &m);
  16. 	for(int i = 0; i < m; i++) scanf("%d", &a[i]);
  17. 	for(int i = 0; i < (1 << m); i++) {
  18. 		long long res = 1;
  19. 		for(int j = 0; j < m; j++) {
  20. 			if(i & (1 << j)) {
  21. 				res *= a[j];
  22. 				if(res > n) break;
  23. 			}
  24. 		}
  25. 		if(res <= n) v.push_back(res);
  26. 	}
  27. 	sort(v.begin(), v.end());
  28. 	v = unique(v);
  29. 	int ret = 0;
  30. 	for(int i = 0; i < v.size(); i++) {
  31. 		long long r = v[i];
  32. 		for(int j = 0; j < m; j++) {
  33. 			if(v[i] % a[j] == 0) v[i] /= a[j];
  34. 		}
  35. 		if(v[i] == 1) ret++;
  36. 	}
  37. 	printf("%d\n", ret);
  38. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
7 2
3
6
stdout
copy 
2
https://ideone.com/ZbhQMn
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!