結果
| 問題 |
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';
}