結果
問題 | No.1059 素敵な集合 |
ユーザー |
![]() |
提出日時 | 2020-05-30 18:13:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 36 ms / 2,000 ms |
コード長 | 2,750 bytes |
コンパイル時間 | 5,634 ms |
コンパイル使用メモリ | 125,008 KB |
最終ジャッジ日時 | 2025-01-10 19:39:45 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <iostream>#include <string>#include <algorithm>#include <functional>#include <vector>#include <stack>#include <queue>#include <deque>#include <set>#include <map>#include <cstdio>#include <cmath>#include <tuple>#include <iomanip>#include <numeric>#include <unordered_map>#include <sstream>#include<limits.h>#include<float.h>#include<list>#include <array>#include <complex>#include<stdio.h>#include<string.h>#include <bitset>#include<assert.h>using namespace std;#define int long long#define I32_MAX 2147483647#define I64_MAX 9223372036854775807LL#define I64_MAX2 1223372036854775807LL#define INF I64_MAX2#define MOD 1000000007#define MEM_SIZE 10000#define DEBUG_OUT true#define ALL(x) (x).begin(), (x).end()template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; abort();}}template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }class DisjointSet{public:vector<int> rank,p;DisjointSet(){}DisjointSet(int size){rank.resize(size,0);p.resize(size,0);for (int i = 0; i < size; i++){makeSet(i);}}void makeSet(int x){p[x] = x;rank[x] = 0;}bool same(int x, int y){return findSet(x) == findSet(y);}void unite(int x, int y){link(findSet(x),findSet(y));}void link(int x, int y){if(rank[x] > rank[y]){p[y] = p[x];}else{p[x] = p[y];}if(rank[x] == rank[y]){rank[y]++;}}int findSet(int x){if(x != p[x]){p[x] = findSet(p[x]);}return p[x];}};void solve(void){int L,R;cin>>L>>R;DisjointSet DS(R+1);for (int x = L; x < R+1; x++){int cnt = R/x;int add = cnt;for (int i = 2; i <= cnt; i++){DS.unite(x,i*x);}}set<int> SET;for (int i = L; i <= R; i++){SET.insert(DS.findSet(i));}cout<<SET.size()-1<<endl;return;}int32_t main(int32_t argc, const char *argv[]){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout << std::fixed;std::cout << std::setprecision(11);solve();return 0;}