結果
問題 | No.1059 素敵な集合 |
ユーザー |
![]() |
提出日時 | 2020-05-22 22:23:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 13 ms / 2,000 ms |
コード長 | 1,009 bytes |
コンパイル時間 | 1,684 ms |
コンパイル使用メモリ | 170,368 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-23 09:31:04 |
合計ジャッジ時間 | 2,563 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i = 0; i < (int)n; i++) using ll = long long; class Union_Find{ vector<int> par; vector<int> rank; vector<int> num; public: Union_Find(int n) { par = vector<int>(n); rank = vector<int>(n,0); num = vector<int>(n,1); rep(i,n) par[i] = i; } int find(int x) { if(par[x] == x) return x; else return par[x] = find(par[x]); } int number(int x) { return num[find(x)]; } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (rank[x] < rank[y]) swap(x, y); if (rank[x] == rank[y]) rank[x]++; par[y] = x; num[x] += num[y]; } bool same(int x, int y) { return find(x) == find(y); } }; int main(){ ll l, r; cin >> l >> r; Union_Find uf(r+1); for(int i = l; i <= r; i++) { for(int j = 1; j*i <= r; j++) uf.unite(i,i*j); } int ans = -1; for(int i = l; i <= r; i++) { if(uf.find(i) == i) ans++; } cout << ans << endl; return 0; }