結果
問題 | No.1653 Squarefree |
ユーザー |
|
提出日時 | 2021-09-02 11:29:26 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 812 bytes |
コンパイル時間 | 6,752 ms |
コンパイル使用メモリ | 265,656 KB |
最終ジャッジ日時 | 2025-01-24 04:23:51 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | WA * 8 TLE * 21 MLE * 9 |
ソースコード
#include <bits/stdc++.h>using namespace std;map <long long int, bool> isprime;vector <long long int> prime;map <long long int, bool> check;int main(void){long long int a, b;int count = 0;cin.tie(0);ios::sync_with_stdio(false);cin >> a >> b;for (long long int i = 2; i <= (long long int)sqrt(b); i++){if (isprime[i]){prime.push_back(i);for (long long int j = 2 * i; j <= (long long int)sqrt(b); j += i){isprime[j] = false;}}}for (int i = 0; i < prime.size(); i++){long long int x = prime[i] * prime[i];long long int l = ceil((a - 1) / x + 1) * x;for (long long int j = l; j <= b; j += x){if (check[(int)(j - a)] == false){check[(int)(j - a)] = true;count++;}}}cout << (b - a + 1) - count << '\n';return 0;}