結果
問題 | No.1059 素敵な集合 |
ユーザー |
![]() |
提出日時 | 2020-05-22 23:06:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 203 ms / 2,000 ms |
コード長 | 1,344 bytes |
コンパイル時間 | 1,630 ms |
コンパイル使用メモリ | 172,620 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-23 09:32:45 |
合計ジャッジ時間 | 3,588 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <bits/stdc++.h>#define REP(i, n) for(int i = 0; (i) < (n); (i)++)using namespace std;bool check[200005];int L, R;typedef pair<int, int> P;int main(){cin >> L >> R;REP(i, R+1) check[i] = false;int ans = 0;for(int i=L;i<=R;i++){if(check[i]) continue;ans++;queue<P> que;que.push(P(i, 0));check[i] = true;while(!que.empty()){P p = que.front(); que.pop();if(p.second == 0){for(int j=2; p.first * j <= R; j++){if(!check[p.first*j]){check[p.first*j] = true;que.push(P(p.first * j, 1));}}}else{for(int j=2; j*j <= p.first; j++){if(p.first%j==0){if(!check[p.first/j] && p.first/j>=L){check[p.first/j] = true;que.push(P(p.first/j, 0));}if(!check[j] && j>=L){check[j] = true;que.push(P(j, 0));}}}}}}cout << ans-1 << endl;return 0;}