結果

問題 No.1059 素敵な集合
ユーザー theory_and_metheory_and_me
提出日時 2020-05-23 13:05:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 34 ms / 2,000 ms
コード長 2,572 bytes
コンパイル時間 2,801 ms
コンパイル使用メモリ 199,844 KB
最終ジャッジ日時 2025-01-10 15:18:15
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//typedef vector<vector<ll>> Graph;
const ll mod = 1e9 + 7;
//const ll mod = 998244353;
#define REP(i,n) for(ll i=0;i<(ll)n;i++)
#define dump(x) cerr << #x << " = " << (x) << endl;
#define spa << " " <<
#define fi first
#define se second
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<typename T> void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cerr<<v[i][0];for(ll j=1;j<w;j++)cerr spa v[i][j];cerr<<endl;}};
template<typename T> void debug(vector<T>&v,ll n){if(n!=0)cerr<<v[0];
for(ll i=1;i<n;i++)cerr spa v[i];
cerr<<endl;};
string num2bit(ll num, ll len){
string bit = "";
REP(i, len){
bit += char('0'+(num>>i & 1));
}
return bit;
}
struct UnionFindSize {
vector<int> par;
UnionFindSize(int n) : par(n, -1) { }
void init(int n) { par.assign(n, -1); }
int root(int x) {
if (par[x] < 0) return x;
else return par[x] = root(par[x]);
}
bool issame(int x, int y) {
return root(x) == root(y);
}
bool merge(int x, int y) {
x = root(x); y = root(y);
if (x == y) return false;
if (par[x] > par[y]) swap(x, y); // merge technique
par[x] += par[y];
par[y] = x;
return true;
}
int size(int x) {
return -par[root(x)];
}
void print(){
cout << "uf: ";
for(int i=0;i<(int)par.size();i++) cout << root(i) << " ";
cout << endl;
}
};
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
ll L, R;
cin >> L >> R;
UnionFindSize uf(R-L+1);
for(int i=L;i<=R;i++){
for(int j=2;i*j<=R;j++){
uf.merge(i-L, i*j-L);
}
}
set<ll> st;
REP(i, R-L+1) st.insert(uf.root(i));
cout << (int)st.size()-1 << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0