結果
問題 | No.1653 Squarefree |
ユーザー | otera |
提出日時 | 2022-04-03 10:20:37 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 244 ms / 2,000 ms |
コード長 | 8,305 bytes |
コンパイル時間 | 2,551 ms |
コンパイル使用メモリ | 212,668 KB |
実行使用メモリ | 16,916 KB |
最終ジャッジ日時 | 2024-05-02 12:22:41 |
合計ジャッジ時間 | 10,703 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 239 ms
16,908 KB |
testcase_01 | AC | 22 ms
9,032 KB |
testcase_02 | AC | 21 ms
8,904 KB |
testcase_03 | AC | 22 ms
9,032 KB |
testcase_04 | AC | 22 ms
8,900 KB |
testcase_05 | AC | 22 ms
9,032 KB |
testcase_06 | AC | 21 ms
9,032 KB |
testcase_07 | AC | 21 ms
8,904 KB |
testcase_08 | AC | 22 ms
9,032 KB |
testcase_09 | AC | 21 ms
9,160 KB |
testcase_10 | AC | 22 ms
9,032 KB |
testcase_11 | AC | 222 ms
16,832 KB |
testcase_12 | AC | 217 ms
16,840 KB |
testcase_13 | AC | 232 ms
16,740 KB |
testcase_14 | AC | 233 ms
16,668 KB |
testcase_15 | AC | 242 ms
16,844 KB |
testcase_16 | AC | 244 ms
16,756 KB |
testcase_17 | AC | 237 ms
16,828 KB |
testcase_18 | AC | 231 ms
16,768 KB |
testcase_19 | AC | 232 ms
16,828 KB |
testcase_20 | AC | 230 ms
16,840 KB |
testcase_21 | AC | 241 ms
16,844 KB |
testcase_22 | AC | 233 ms
16,840 KB |
testcase_23 | AC | 234 ms
16,592 KB |
testcase_24 | AC | 237 ms
16,844 KB |
testcase_25 | AC | 233 ms
16,792 KB |
testcase_26 | AC | 238 ms
16,712 KB |
testcase_27 | AC | 238 ms
16,840 KB |
testcase_28 | AC | 229 ms
16,836 KB |
testcase_29 | AC | 239 ms
16,916 KB |
testcase_30 | AC | 241 ms
16,740 KB |
testcase_31 | AC | 240 ms
16,652 KB |
testcase_32 | AC | 235 ms
16,840 KB |
testcase_33 | AC | 230 ms
16,836 KB |
testcase_34 | AC | 241 ms
16,876 KB |
testcase_35 | AC | 233 ms
16,840 KB |
testcase_36 | AC | 22 ms
9,032 KB |
testcase_37 | AC | 22 ms
9,032 KB |
testcase_38 | AC | 21 ms
9,028 KB |
testcase_39 | AC | 21 ms
9,076 KB |
testcase_40 | AC | 21 ms
9,160 KB |
ソースコード
/** * author: otera **/ #include<bits/stdc++.h> namespace otera { struct Eratos { public: Eratos() : Eratos(0) {} Eratos(int N) { init(N); } void init(int N) { _N = N; _primes.clear(); _isprime.assign(_N + 1, true); _min_factor.assign(_N + 1, -1); _isprime[0] = _isprime[1] = false; _min_factor[0] = 0, _min_factor[1] = 1; for (int i = 2; i <= _N; ++i) { if (!_isprime[i]) continue; _primes.push_back(i); _min_factor[i] = i; for (int j = i * 2; j <= _N; j += i) { _isprime[j] = false; if (_min_factor[j] == -1) _min_factor[j] = i; } } } bool isprime(int n) { assert(0 <= n and n <= _N); return _isprime[n]; } std::vector<int> primes() { return _primes; } std::vector<std::pair<int,int>> prime_factors(int n) { std::vector<std::pair<int,int>> res; while (n != 1) { int prime = _min_factor[n]; int exp = 0; while (_min_factor[n] == prime) { ++exp; n /= prime; } res.push_back(std::make_pair(prime, exp)); } return res; } std::vector<int> divisors(int n) { std::vector<int> res({1}); auto pf = prime_factors(n); for (auto p :pf) { int n = (int)res.size(); for (int i = 0; i < n; ++i) { int v = 1; for (int j = 0; j < p.second; ++j) { v *= p.first; res.push_back(res[i] * v); } } } return res; } private: int _N; std::vector<int> _primes; std::vector<bool> _isprime; std::vector<int> _min_factor; }; } // namespace otera using namespace std; #define int long long using ll = long long; using ld = long double; using ull = unsigned long long; using int128_t = __int128_t; #define repa(i, n) for(int i = 0; i < n; ++ i) #define repb(i, a, b) for(int i = a; i < b; ++ i) #define repc(i, a, b, c) for(int i = a; i < b; i += c) #define overload4(a, b, c, d, e, ...) e #define overload3(a, b, c, d, ...) d #define rep(...) overload4(__VA_ARGS__, repc, repb, repa)(__VA_ARGS__) #define rep1a(i, n) for(int i = 0; i <= n; ++ i) #define rep1b(i, a, b) for(int i = a; i <= b; ++ i) #define rep1c(i, a, b, c) for(int i = a; i <= b; i += c) #define rep1(...) overload4(__VA_ARGS__, rep1c, rep1b, rep1a)(__VA_ARGS__) #define rev_repa(i, n) for(int i=n-1;i>=0;i--) #define rev_repb(i, a, b) assert(a > b);for(int i=a;i>b;i--) #define rev_rep(...) overload3(__VA_ARGS__, rev_repb, rev_repa)(__VA_ARGS__) #define rev_rep1a(i, n) for(int i=n;i>=1;i--) #define rev_rep1b(i, a, b) assert(a >= b);for(int i=a;i>=b;i--) #define rev_rep1(...) overload3(__VA_ARGS__, rev_rep1b, rev_rep1a)(__VA_ARGS__) typedef pair<int, int> P; typedef pair<ll, ll> LP; #define pb push_back #define pf push_front #define ppb pop_back #define ppf pop_front #define eb emplace_back #define fr first #define sc second #define all(c) c.begin(),c.end() #define rall(c) c.rbegin(), c.rend() #define lb(c, x) distance((c).begin(), lower_bound(all(c), (x))) #define ub(c, x) distance((c).begin(), upper_bound(all(c), (x))) #define Sort(a) sort(all(a)) #define Rev(a) reverse(all(a)) #define Uniq(a) sort(all(a));a.erase(unique(all(a)),end(a)) #define si(c) (int)(c).size() inline ll popcnt(ull a){ return __builtin_popcountll(a); } #define kth_bit(x, k) ((x>>k)&1) #define unless(A) if(!(A)) ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; } ll intpow(ll a, ll b, ll m) {ll ans = 1; while(b){ if(b & 1) (ans *= a) %= m; (a *= a) %= m; b /= 2; } return ans; } template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } #define INT(...) int __VA_ARGS__;in(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;in(__VA_ARGS__) #define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__) #define STR(...) string __VA_ARGS__;in(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;in(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;in(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;in(__VA_ARGS__) #define vec(type,name,...) vector<type>name(__VA_ARGS__) #define VEC(type,name,size) vector<type>name(size);in(name) #define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__)) #define VV(type,name,h,w) vector<vector<type>>name(h,vector<type>(w));in(name) #define vvv(type,name,h,w,...) vector<vector<vector<type>>>name(h,vector<vector<type>>(w,vector<type>(__VA_ARGS__))) template <class T> using vc = vector<T>; template <class T> using vvc = vector<vc<T>>; template <class T> using vvvc = vector<vvc<T>>; template <class T> using vvvvc = vector<vvvc<T>>; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; template <class T, class U> using umap = unordered_map<T, U>; template<class T> void scan(T& a){ cin >> a; } template<class T> void scan(vector<T>& a){ for(auto&& i : a) scan(i); } void in(){} template <class Head, class... Tail> void in(Head& head, Tail&... tail){ scan(head); in(tail...); } void print(){ cout << ' '; } template<class T> void print(const T& a){ cout << a; } template<class T> void print(const vector<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ cout << ' '; print(*i); } } int out(){ cout << '\n'; return 0; } template<class T> int out(const T& t){ print(t); cout << '\n'; return 0; } template<class Head, class... Tail> int out(const Head& head, const Tail&... tail){ print(head); cout << ' '; out(tail...); return 0; } #define CHOOSE(a) CHOOSE2 a #define CHOOSE2(a0,a1,a2,a3,a4,x,...) x #define debug_1(x1) cout<<#x1<<": "<<x1<<endl #define debug_2(x1,x2) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<endl #define debug_3(x1,x2,x3) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<endl #define debug_4(x1,x2,x3,x4) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<endl #define debug_5(x1,x2,x3,x4,x5) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<endl #ifdef DEBUG #define debug(...) CHOOSE((__VA_ARGS__,debug_5,debug_4,debug_3,debug_2,debug_1,~))(__VA_ARGS__) #define dump(...) { print(#__VA_ARGS__); print(":"); out(__VA_ARGS__); } #else #define debug(...) #define dump(...) #endif struct io_setup { io_setup(int precision = 20) { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(precision); } } io_setup_ {}; constexpr int N = 1'010'000; bool check[N]; ll val[N]; void solve() { otera::Eratos er(N); rep(i, N) check[i] = 1; auto ps = er.primes(); LL(l, r); for(ll i = l; i <= r; ++ i) { val[i - l] = i; } for(ll p: ps) { for(ll i = (l + p - 1) / p * p; i <= r; i += p) { int cnt = 0; while(val[i - l] % p == 0) { val[i - l] /= p; ++ cnt; } if(cnt >= 2) check[i - l] = 0; } } int ans = 0; for(ll i = l; i <= r; ++ i) { debug(i, check[i - l], val[i - l]); unless(check[i - l]) continue; ll sq = (ll)sqrt((ld)val[i - l]); int ok = 1; if(val[i - l] == 1) { ans += ok; continue; } for(int j = sq - 3; j <= sq + 3; ++ j) { if(j * j == val[i - l]) { ok = 0; } } ans += ok; } out(ans); } signed main() { int testcase = 1; // in(testcase); while(testcase--) solve(); return 0; }