結果
問題 | No.1653 Squarefree |
ユーザー |
![]() |
提出日時 | 2021-06-13 04:07:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 271 ms / 2,000 ms |
コード長 | 922 bytes |
コンパイル時間 | 722 ms |
コンパイル使用メモリ | 69,484 KB |
最終ジャッジ日時 | 2025-01-22 07:52:38 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <iostream> #include <bitset> using namespace std; typedef long long ll; const int MAX=1000010; bitset<MAX> isprime; void sieve(){ for(int i=3; i<MAX; i++, i++) isprime[i]=1; isprime[2]=1; for(int i=3; i<MAX; i++){ if(isprime[i]){ for(int j=(i<<1); j<MAX; j+=i) isprime[j]=0; } } } ll x[MAX]; bitset<MAX> sqf; int main() { ll l, r; cin>>l>>r; sieve(); for(ll i=l; i<=r; i++){ x[i-l]=i; sqf[i-l]=1; } for(ll p=2; p<MAX; p++){ if(!isprime[p]) continue; for(ll i=(l+p-1)/p*p; i<=r; i+=p){ int e=0; while(x[i-l]%p==0){ x[i-l]/=p; e++; } if(e>1) sqf[i-l]=0; } } int ans=0; for(ll i=l; i<=r; i++){ if(!sqf[i-l]) continue; if(x[i-l]==1){ ans++; continue; } ll xl=1, xr=1e9+7; while(xr-xl>1){ ll xm=(xl+xr)/2; if(xm*xm<=x[i-l]) xl=xm; else xr=xm; } if(xl*xl!=x[i-l]) ans++; } cout<<ans<<endl; return 0; }