結果
問題 | No.1653 Squarefree |
ユーザー | nok0 |
提出日時 | 2021-08-20 22:42:57 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 483 ms / 2,000 ms |
コード長 | 12,053 bytes |
コンパイル時間 | 4,515 ms |
コンパイル使用メモリ | 267,576 KB |
実行使用メモリ | 21,632 KB |
最終ジャッジ日時 | 2024-10-14 08:26:11 |
合計ジャッジ時間 | 18,429 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 479 ms
21,564 KB |
testcase_01 | AC | 32 ms
14,084 KB |
testcase_02 | AC | 21 ms
14,084 KB |
testcase_03 | AC | 31 ms
13,972 KB |
testcase_04 | AC | 31 ms
14,088 KB |
testcase_05 | AC | 30 ms
14,216 KB |
testcase_06 | AC | 29 ms
14,088 KB |
testcase_07 | AC | 30 ms
14,092 KB |
testcase_08 | AC | 31 ms
14,216 KB |
testcase_09 | AC | 31 ms
14,084 KB |
testcase_10 | AC | 31 ms
14,092 KB |
testcase_11 | AC | 366 ms
21,528 KB |
testcase_12 | AC | 384 ms
21,548 KB |
testcase_13 | AC | 464 ms
21,424 KB |
testcase_14 | AC | 449 ms
21,536 KB |
testcase_15 | AC | 455 ms
21,580 KB |
testcase_16 | AC | 442 ms
21,476 KB |
testcase_17 | AC | 462 ms
21,484 KB |
testcase_18 | AC | 469 ms
21,576 KB |
testcase_19 | AC | 456 ms
21,484 KB |
testcase_20 | AC | 470 ms
21,544 KB |
testcase_21 | AC | 459 ms
21,584 KB |
testcase_22 | AC | 452 ms
21,552 KB |
testcase_23 | AC | 458 ms
21,412 KB |
testcase_24 | AC | 459 ms
21,472 KB |
testcase_25 | AC | 459 ms
21,632 KB |
testcase_26 | AC | 449 ms
21,432 KB |
testcase_27 | AC | 465 ms
21,624 KB |
testcase_28 | AC | 471 ms
21,524 KB |
testcase_29 | AC | 459 ms
21,576 KB |
testcase_30 | AC | 483 ms
21,416 KB |
testcase_31 | AC | 472 ms
21,560 KB |
testcase_32 | AC | 475 ms
21,508 KB |
testcase_33 | AC | 476 ms
21,492 KB |
testcase_34 | AC | 476 ms
21,504 KB |
testcase_35 | AC | 467 ms
21,500 KB |
testcase_36 | AC | 29 ms
14,088 KB |
testcase_37 | AC | 29 ms
14,216 KB |
testcase_38 | AC | 30 ms
14,084 KB |
testcase_39 | AC | 29 ms
14,216 KB |
testcase_40 | AC | 29 ms
14,216 KB |
ソースコード
#line 1 "/Users/nok0/Documents/Programming/nok0/math/osa_k.hpp" #include <vector> struct osa_k { private: std::vector<int> spf, pr; public: osa_k() = default; osa_k(int MAX) : spf(MAX + 1) { for(int i = 2; i <= MAX; i++) { if(spf[i] == 0) { spf[i] = i; pr.push_back(i); } for(int j = 0; j < pr.size() and pr[j] <= spf[i] and i * pr[j] <= MAX; j++) spf[i * pr[j]] = pr[j]; } } std::vector<std::pair<int, int>> PF(int n) { std::vector<std::pair<int, int>> divisor; if(n == 1) return divisor; int before = spf[n], cnt = 0; while(n > 1) { if(spf[n] == before) { cnt++; n /= spf[n]; } else { divisor.emplace_back(before, cnt); before = spf[n]; cnt = 1; n /= spf[n]; } } divisor.emplace_back(before, cnt); return divisor; } int smallestprimefactor(const int n) const { return spf[n]; } bool isPrime(const int n) const { return n == spf[n]; } }; #line 1 "/Users/nok0/Documents/Programming/nok0/template.hpp" #include <bits/stdc++.h> using namespace std; #if __has_include(<atcoder/all>) #include <atcoder/all> using namespace atcoder; #endif #pragma region Macros // rep macro #define foa(v, a) for(auto &v : a) #define REPname(a, b, c, d, e, ...) e #define REP(...) REPname(__VA_ARGS__, REP3, REP2, REP1, REP0)(__VA_ARGS__) #define REP0(x) for(int i = 0; i < (x); ++i) #define REP1(i, x) for(int i = 0; i < (x); ++i) #define REP2(i, l, r) for(int i = (l); i < (r); ++i) #define REP3(i, l, r, c) for(int i = (l); i < (r); i += (c)) #define REPSname(a, b, c, ...) c #define REPS(...) REPSname(__VA_ARGS__, REPS1, REPS0)(__VA_ARGS__) #define REPS0(x) for(int i = 1; i <= (x); ++i) #define REPS1(i, x) for(int i = 1; i <= (x); ++i) #define RREPname(a, b, c, d, e, ...) e #define RREP(...) RREPname(__VA_ARGS__, RREP3, RREP2, RREP1, RREP0)(__VA_ARGS__) #define RREP0(x) for(int i = (x)-1; i >= 0; --i) #define RREP1(i, x) for(int i = (x)-1; i >= 0; --i) #define RREP2(i, r, l) for(int i = (r)-1; i >= (l); --i) #define RREP3(i, r, l, c) for(int i = (r)-1; i >= (l); i -= (c)) #define RREPSname(a, b, c, ...) c #define RREPS(...) RREPSname(__VA_ARGS__, RREPS1, RREPS0)(__VA_ARGS__) #define RREPS0(x) for(int i = (x); i >= 1; --i) #define RREPS1(i, x) for(int i = (x); i >= 1; --i) // name macro #define pb push_back #define eb emplace_back #define SZ(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define popcnt(x) __builtin_popcountll(x) template <class T = int> using V = std::vector<T>; template <class T = int> using VV = std::vector<std::vector<T>>; template <class T> using pqup = std::priority_queue<T, std::vector<T>, std::greater<T>>; using ll = long long; using ld = long double; using int128 = __int128_t; using pii = std::pair<int, int>; using pll = std::pair<long long, long long>; // input macro template <class T, class U> std::istream &operator>>(std::istream &is, std::pair<T, U> &p) { is >> p.first >> p.second; return is; } template <class T> std::istream &operator>>(std::istream &is, std::vector<T> &v) { for(T &i : v) is >> i; return is; } std::istream &operator>>(std::istream &is, __int128_t &a) { std::string s; is >> s; __int128_t ret = 0; for(int i = 0; i < s.length(); i++) if('0' <= s[i] and s[i] <= '9') ret = 10 * ret + s[i] - '0'; a = ret * (s[0] == '-' ? -1 : 1); return is; } #if __has_include(<atcoder/all>) std::istream &operator>>(std::istream &is, atcoder::modint998244353 &a) { long long v; is >> v; a = v; return is; } std::istream &operator>>(std::istream &is, atcoder::modint1000000007 &a) { long long v; is >> v; a = v; return is; } template <int m> std::istream &operator>>(std::istream &is, atcoder::static_modint<m> &a) { long long v; is >> v; a = v; return is; } template <int m> std::istream &operator>>(std::istream &is, atcoder::dynamic_modint<m> &a) { long long v; is >> v; a = v; return is; } #endif namespace scanner { void scan(int &a) { std::cin >> a; } void scan(long long &a) { std::cin >> a; } void scan(std::string &a) { std::cin >> a; } void scan(char &a) { std::cin >> a; } void scan(char a[]) { std::scanf("%s", a); } void scan(double &a) { std::cin >> a; } void scan(long double &a) { std::cin >> a; } template <class T, class U> void scan(std::pair<T, U> &p) { std::cin >> p; } template <class T> void scan(std::vector<T> &a) { std::cin >> a; } void INPUT() {} template <class Head, class... Tail> void INPUT(Head &head, Tail &... tail) { scan(head); INPUT(tail...); } } // namespace scanner #define VEC(type, name, size) \ std::vector<type> name(size); \ scanner::INPUT(name) #define VVEC(type, name, h, w) \ std::vector<std::vector<type>> name(h, std::vector<type>(w)); \ scanner::INPUT(name) #define INT(...) \ int __VA_ARGS__; \ scanner::INPUT(__VA_ARGS__) #define LL(...) \ long long __VA_ARGS__; \ scanner::INPUT(__VA_ARGS__) #define STR(...) \ std::string __VA_ARGS__; \ scanner::INPUT(__VA_ARGS__) #define CHAR(...) \ char __VA_ARGS__; \ scanner::INPUT(__VA_ARGS__) #define DOUBLE(...) \ double __VA_ARGS__; \ scanner::INPUT(__VA_ARGS__) #define LD(...) \ long double __VA_ARGS__; \ scanner::INPUT(__VA_ARGS__) // output-macro template <class T, class U> std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p) { os << p.first << " " << p.second; return os; } template <class T> std::ostream &operator<<(std::ostream &os, const std::vector<T> &a) { for(int i = 0; i < int(a.size()); ++i) { if(i) os << " "; os << a[i]; } return os; } std::ostream &operator<<(std::ostream &dest, __int128_t &value) { std::ostream::sentry s(dest); if(s) { __uint128_t tmp = value < 0 ? -value : value; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while(tmp != 0); if(value < 0) { --d; *d = '-'; } int len = std::end(buffer) - d; if(dest.rdbuf()->sputn(d, len) != len) { dest.setstate(std::ios_base::badbit); } } return dest; } #if __has_include(<atcoder/all>) std::ostream &operator<<(std::ostream &os, const atcoder::modint998244353 &a) { return os << a.val(); } std::ostream &operator<<(std::ostream &os, const atcoder::modint1000000007 &a) { return os << a.val(); } template <int m> std::ostream &operator<<(std::ostream &os, const atcoder::static_modint<m> &a) { return os << a.val(); } template <int m> std::ostream &operator<<(std::ostream &os, const atcoder::dynamic_modint<m> &a) { return os << a.val(); } #endif template <class T> void print(const T a) { std::cout << a << '\n'; } template <class Head, class... Tail> void print(Head H, Tail... T) { std::cout << H << ' '; print(T...); } template <class T> void printel(const T a) { std::cout << a << '\n'; } template <class T> void printel(const std::vector<T> &a) { for(const auto &v : a) std::cout << v << '\n'; } template <class Head, class... Tail> void printel(Head H, Tail... T) { std::cout << H << '\n'; printel(T...); } void Yes(const bool b = true) { std::cout << (b ? "Yes\n" : "No\n"); } void No() { std::cout << "No\n"; } void YES(const bool b = true) { std::cout << (b ? "YES\n" : "NO\n"); } void NO() { std::cout << "NO\n"; } void err(const bool b = true) { if(b) { std::cout << "-1\n", exit(0); } } //debug macro namespace debugger { template <class T> void view(const std::vector<T> &a) { std::cerr << "{ "; for(const auto &v : a) { std::cerr << v << ", "; } std::cerr << "\b\b }"; } template <class T> void view(const std::vector<std::vector<T>> &a) { std::cerr << "{\n"; for(const auto &v : a) { std::cerr << "\t"; view(v); std::cerr << "\n"; } std::cerr << "}"; } template <class T, class U> void view(const std::vector<std::pair<T, U>> &a) { std::cerr << "{\n"; for(const auto &p : a) std::cerr << "\t(" << p.first << ", " << p.second << ")\n"; std::cerr << "}"; } template <class T, class U> void view(const std::map<T, U> &m) { std::cerr << "{\n"; for(const auto &p : m) std::cerr << "\t[" << p.first << "] : " << p.second << "\n"; std::cerr << "}"; } template <class T, class U> void view(const std::pair<T, U> &p) { std::cerr << "(" << p.first << ", " << p.second << ")"; } template <class T> void view(const std::set<T> &s) { std::cerr << "{ "; for(auto &v : s) { view(v); std::cerr << ", "; } std::cerr << "\b\b }"; } template <class T> void view(const T &e) { std::cerr << e; } } // namespace debugger #ifdef LOCAL void debug_out() {} template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { debugger::view(H); std::cerr << ", "; debug_out(T...); } #define debug(...) \ do { \ std::cerr << __LINE__ << " [" << #__VA_ARGS__ << "] : ["; \ debug_out(__VA_ARGS__); \ std::cerr << "\b\b]\n"; \ } while(false) #else #define debug(...) (void(0)) #endif // vector macro template <class T> int lb(const std::vector<T> &a, const T x) { return std::distance((a).begin(), std::lower_bound((a).begin(), (a).end(), (x))); } template <class T> int ub(const std::vector<T> &a, const T x) { return std::distance((a).begin(), std::upper_bound((a).begin(), (a).end(), (x))); } template <class T> void UNIQUE(std::vector<T> &a) { std::sort(a.begin(), a.end()); a.erase(std::unique(a.begin(), a.end()), a.end()); } template <class T> std::vector<T> press(std::vector<T> &a) { auto res = a; UNIQUE(res); for(auto &v : a) v = lb(res, v); return res; } #define SORTname(a, b, c, ...) c #define SORT(...) SORTname(__VA_ARGS__, SORT1, SORT0, ...)(__VA_ARGS__) #define SORT0(a) std::sort((a).begin(), (a).end()) #define SORT1(a, c) std::sort((a).begin(), (a).end(), [](const auto x, const auto y) { return x c y; }) template <class T> void ADD(std::vector<T> &a, const T x = 1) { for(auto &v : a) v += x; } template <class T> void SUB(std::vector<T> &a, const T x = 1) { for(auto &v : a) v -= x; } template <class T> void MUL(std::vector<T> &a, const T x) { for(auto &v : a) v *= x; } template <class T> void DIV(std::vector<T> &a, const T x) { for(auto &v : a) v /= x; } // math macro template <class T, class U> inline bool chmin(T &a, const U &b) { return a > b ? a = b, true : false; } template <class T, class U> inline bool chmax(T &a, const U &b) { return a < b ? a = b, true : false; } template <class T> T divup(T x, T y) { return (x + y - 1) / y; } template <class T> T POW(T a, long long n) { T ret = 1; while(n) { if(n & 1) ret *= a; a *= a; n >>= 1; } return ret; } // modpow long long POW(long long a, long long n, const int mod) { long long ret = 1; a = (a % mod + mod) % mod; while(n) { if(n & 1) (ret *= a) %= mod; (a *= a) %= mod; n >>= 1; } return ret; } // others struct fast_io { fast_io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); } } fast_io_; const int inf = 1e9; const ll INF = 1e18; #pragma endregion void main_(); int main() { main_(); return 0; } #line 3 "d.cpp" int res; const int M = 2000000; bool sq_free[M + 1]; ll my_sqrt(ll n) { int128 ok = INF, ng = 0; while(ok - ng > 1) { int128 mid = (ok + ng) / 2; if(mid * mid >= n) ok = mid; else ng = mid; } return (ll)ok; } void main_() { REP(M + 1) { sq_free[i] = 1; } osa_k pf(M); LL(l, r); if(l == 1) { if(r == 1) { print(1); return; } res++; l = 2; } V<ll> val(r - l + 1); iota(all(val), l); for(ll i = 2; i <= M; i++) { if(!pf.isPrime(i)) continue; ll v = i * i; ll lb = divup(l, v); for(ll j = v * lb; j <= r; j += v) { sq_free[j - l] = 0; } } for(ll i = 2; i <= M; i++) { if(!pf.isPrime(i)) continue; ll lb = divup(l, i); for(ll j = i * lb; j <= r; j += i) { while(val[j - l] % i == 0) { val[j - l] /= i; } } } REP(i, r - l + 1) { if(sq_free[i]) { ll u = my_sqrt(val[i]); res += (u * u != val[i]) or val[i] == 1; } } print(res); }