結果
問題 |
No.1946 ロッカーの問題
|
ユーザー |
|
提出日時 | 2022-05-20 22:26:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 707 ms / 3,000 ms |
コード長 | 1,074 bytes |
コンパイル時間 | 2,011 ms |
コンパイル使用メモリ | 199,888 KB |
最終ジャッジ日時 | 2025-01-29 10:56:19 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; #define rep(i, a, b) for(ll i = (ll)a; i < (ll)b; i++) #define irep(i, v) for(auto i = (v).begin(); i != (v).end(); i++) #define ALL(v) (v).begin(), (v).end() #define SZ(v) (ll)(v).size() const ll INF = 1e18; const ld EPS = 1e-10; const ll MOD = 1e9 + 7; const ld PI = M_PI; vector<ll> factor_array(ll n){ vector<ll> res; for(ll i = 1; i * i <= n; i++){ if(n % i == 0){ res.push_back(i); if(i * i != n) res.push_back(n / i); } } sort(res.begin(), res.end()); return res; } int main(){ cin.tie(0); ios::sync_with_stdio(false); srand((unsigned)time(NULL)); cout << fixed << setprecision(20); ll n, m; cin >> n >> m; vector<ll> cnt(n + 1, 0); rep(i, 0, m){ ll a; cin >> a; cnt[a]++; } ll ans = 0; for(ll i = n; i >= 1; i--){ if(cnt[i] % 2 == 0){ ans++; } else{ auto fa = factor_array(i); rep(j, 0, SZ(fa)){ cnt[fa[j]]++; } } } cout << ans << endl; return 0; }