# Untitled

Feb 16th, 2020
209
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include<bits/stdc++.h>
2. #define TIME cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
3. using namespace std;
4. const int N = 100005;
5.
6. bitset<N> possible, temp, there, lst;
7.
8. int main(){
9. int t=1;
10. while(t--){
11. int n, x; scanf("%d %d", &n, &x);
12. int mn = INT_MAX;
13. there.reset(); possible.reset(); lst.set();
14. for(int i = 0; i < n; i++){
15. int y; scanf("%d", &y);
16. mn = min(mn, y);
17. there[y] = 1;
18. possible[x % y] = 1;
19. }
20. for(int v = N - 1; v >= 1; v--){
21. lst.reset(v);
22. if(!there[v]) continue;
23. // N/64 * log(N / V) calculations
24. temp = possible;
25. for(int j = 0; (1<<j) * v < N; j++) temp |= temp >> ((1 << j) * v);
26. possible |= (temp & lst);
27. }
28. // Using log(N!) ~ N logN - N,
29. // It can be proved that sum_{v=1}^{N} log(N / v) ~ N logN - (N logN - N) ~ N.
30. // So, total bitset operations ~ N.
31. there.reset();
32. for(int i = 0; i < N; i++) if(possible[i]) there[i % mn] = 1;
33. printf("%d\n", (int)there.count());
34. }
35. TIME
36. }
RAW Paste Data