結果
問題 | No.1653 Squarefree |
ユーザー | pockyny |
提出日時 | 2021-08-20 22:14:24 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 319 ms / 2,000 ms |
コード長 | 968 bytes |
コンパイル時間 | 931 ms |
コンパイル使用メモリ | 85,072 KB |
実行使用メモリ | 13,456 KB |
最終ジャッジ日時 | 2024-10-14 08:20:06 |
合計ジャッジ時間 | 10,463 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 296 ms
11,696 KB |
testcase_01 | AC | 13 ms
6,816 KB |
testcase_02 | AC | 13 ms
6,820 KB |
testcase_03 | AC | 14 ms
6,820 KB |
testcase_04 | AC | 13 ms
6,816 KB |
testcase_05 | AC | 13 ms
6,816 KB |
testcase_06 | AC | 13 ms
6,820 KB |
testcase_07 | AC | 13 ms
6,816 KB |
testcase_08 | AC | 13 ms
6,820 KB |
testcase_09 | AC | 13 ms
6,820 KB |
testcase_10 | AC | 13 ms
6,816 KB |
testcase_11 | AC | 245 ms
11,784 KB |
testcase_12 | AC | 255 ms
12,276 KB |
testcase_13 | AC | 285 ms
12,164 KB |
testcase_14 | AC | 279 ms
13,236 KB |
testcase_15 | AC | 283 ms
12,900 KB |
testcase_16 | AC | 279 ms
11,680 KB |
testcase_17 | AC | 285 ms
12,040 KB |
testcase_18 | AC | 277 ms
12,864 KB |
testcase_19 | AC | 286 ms
12,640 KB |
testcase_20 | AC | 280 ms
13,304 KB |
testcase_21 | AC | 294 ms
12,164 KB |
testcase_22 | AC | 297 ms
12,448 KB |
testcase_23 | AC | 298 ms
12,436 KB |
testcase_24 | AC | 300 ms
11,656 KB |
testcase_25 | AC | 319 ms
11,980 KB |
testcase_26 | AC | 312 ms
11,932 KB |
testcase_27 | AC | 316 ms
11,744 KB |
testcase_28 | AC | 308 ms
13,000 KB |
testcase_29 | AC | 298 ms
11,836 KB |
testcase_30 | AC | 300 ms
12,168 KB |
testcase_31 | AC | 301 ms
13,456 KB |
testcase_32 | AC | 286 ms
12,928 KB |
testcase_33 | AC | 303 ms
12,112 KB |
testcase_34 | AC | 287 ms
12,392 KB |
testcase_35 | AC | 299 ms
12,404 KB |
testcase_36 | AC | 13 ms
6,820 KB |
testcase_37 | AC | 13 ms
6,820 KB |
testcase_38 | AC | 13 ms
6,820 KB |
testcase_39 | AC | 13 ms
6,820 KB |
testcase_40 | AC | 13 ms
6,816 KB |
ソースコード
#include <iostream> #include <vector> #include <cmath> using namespace std; typedef long long ll; ll p[1000010]; int main(){ ll i,j,l,r; cin >> l >> r; vector<ll> v; for(i=l;i<=r;i++) v.push_back(i); //v[i] = l + i for(i=2;i<=1000000;i++){ ll ll = (l + i - 1)/i*i; //ll,ll + i,ll + 2*i... for(j=ll;j<=r;j+=i){ if(v[j - l]!=0 && v[j - l]%i==0){ int cnt = 0; while(v[j - l]%i==0){ //cout << v[j - l] << " " << i << endl; v[j - l] /= i; cnt++; } if(cnt>=2) v[j - l] = 0; } } } /*for(i=l;i<=r;i++) cout << i << " "; cout << endl; for(ll x:v) cout << x << " "; cout << endl;*/ int cnt = v.size(); for(ll x:v){ if(x==1) continue; if(x==0) cnt--; else{ ll y = sqrt(x); if(x==y*y) cnt--; } } cout << cnt << endl; }