結果
問題 | No.1059 素敵な集合 |
ユーザー |
![]() |
提出日時 | 2020-05-22 22:37:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 2,000 ms |
コード長 | 2,517 bytes |
コンパイル時間 | 758 ms |
コンパイル使用メモリ | 84,656 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-23 09:31:56 |
合計ジャッジ時間 | 1,582 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <cstdio>#include <string>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <vector>#include <set>#include <map>#include <queue>#include <stack>#include <list>#include <iterator>#include <cassert>#include <numeric>#include <functional>//#include <numeric>#pragma warning(disable:4996)typedef long long ll;typedef unsigned long long ull;#define MIN(a, b) ((a)>(b)? (b): (a))#define MAX(a, b) ((a)<(b)? (b): (a))#define LINF 9223300000000000000#define LINF2 1223300000000000000#define INF 2140000000const long long MOD = 1000000007;//const long long MOD = 998244353;using namespace std;class UF{private:int num;vector<int> par;vector<int> siz;public://vector<int> val;public:UF(int n): num(n) {par.resize(n);siz.resize(n);//val.resize(n);int i;for(i=0; i<n; i++) {par[i]=i; siz[i]=1;//val[i]=0;}}int find(int x) {if(x==par[x]) return x;return par[x] = find(par[x]);}void unite(int x, int y) {x=find(x);y=find(y);if(x==y) return;if(siz[x]<siz[y]) {par[x]=y;siz[y]=siz[x]+siz[y];//val[y]=val[x]+val[y];}else {par[y]=x;siz[x]=siz[x]+siz[y];//val[x]=val[x]+val[y];}}bool same(int x, int y) {return find(x)==find(y);}int size(int x) {return siz[find(x)];}int ngroup() {//int ngroup( int& ans ) {int count=0;int i;for(i=0; i<num; i++) {if(par[i]==i) {count++;//ans += (val[i]? siz[i]: siz[i]-1);}}return count;}};void solve(){int l, r;scanf("%d%d", &l, &r);if (l == 1) {printf("0\n"); return;}UF uf(r - l + 1);int i;for (i = l; i < r / 2 + 3; i++) {int curr = i + i;while (curr <= r) {uf.unite(i-l, curr-l);curr += i;}}int ans = 0;for (i = 0; i < r-l+1; i++) {if (uf.find(i) == i)ans++;}printf("%d\n", ans-1);return;}int main(int argc, char* argv[]){#if 1solve();#elseint T;scanf("%d", &T);int t;for(t=0; t<T; t++) {//printf("Case #%d: ", t+1);solve();}#endifreturn 0;}