Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define endl '\n'
- #define db(x) cerr << #x << " == " << x << endl
- #define dbs(x) cerr << x << endl
- #define st first
- #define nd second
- #define pb push_back
- #define mp make_pair
- #define inf 0x3f3f3f3f
- #define linf 0x3f3f3f3f3f3f3f3f
- typedef long long ll;
- typedef pair <int, int> pii;
- typedef vector <int> vi;
- ll gcd(ll a, ll b){
- return b ? gcd(b, a%b) : a ;
- }
- int main(){
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- int n;
- unordered_set<ll> ans;
- set<ll> d;
- cin >> n;
- while(n--) {
- ll x; cin >> x;
- for(auto it=d.begin(); it!=d.end(); ){
- ll g=gcd(*it, x);
- it=d.erase(it);
- d.insert(g);
- ans.insert(g);
- }
- d.insert(x);
- ans.insert(x);
- }
- cout << ans.size() << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement