結果
問題 |
No.1653 Squarefree
|
ユーザー |
|
提出日時 | 2025-10-02 07:43:21 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 532 ms / 2,000 ms |
コード長 | 1,112 bytes |
コンパイル時間 | 3,619 ms |
コンパイル使用メモリ | 284,152 KB |
実行使用メモリ | 11,220 KB |
最終ジャッジ日時 | 2025-10-02 07:43:41 |
合計ジャッジ時間 | 18,976 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
// #pragma GCC optimize ("Ofast") // #pragma GCC optimize ("unroll-loops") // #pragma GCC target ("avx,avx2,fma") #include <bits/stdc++.h> #define rep(i, a, b) for(int i = (a); i <= (b); i ++) using std::cin, std::cout, std::cerr; using ll = long long; ll Sqrt(ll x) { ll s = std::sqrt(x); while((s + 1) * (s + 1) <= x) s ++; while(s * s > x) s --; return s; } int main() { std::ios::sync_with_stdio(false); ll l, r; cin >> l >> r; ll n = 1e6; std::vector<ll> a(r - l + 1); std::vector<bool> squarefree(r - l + 1, true); std::iota(a.begin(), a.end(), l); for(ll i = 2; i <= n; i ++) { for(ll j = (l + i * i - 1) / (i * i) * (i * i); j <= r; j += i * i) squarefree[j - l] = false; for(ll j = (l + i - 1) / i * i; j <= r; j += i) while(a[j - l] % i == 0) a[j - l] /= i; } for(ll i = l; i <= r; i ++) if(a[i - l] > 1) { ll s = Sqrt(a[i - l]); if(s * s == a[i - l]) squarefree[i - l] = false; } cout << std::ranges::count(squarefree, true) << '\n'; }