結果
問題 | No.1653 Squarefree |
ユーザー |
![]() |
提出日時 | 2021-08-20 22:40:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 791 ms / 2,000 ms |
コード長 | 905 bytes |
コンパイル時間 | 4,704 ms |
コンパイル使用メモリ | 250,524 KB |
最終ジャッジ日時 | 2025-01-24 00:00:52 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000000000000001 bool check(long long n){ long long ok = 1,ng = 1000000001; while(ng-ok>1LL){ long long mid = (ok+ng)/2; if(mid*mid <= n)ok = mid; else ng = mid; } if(ok!=1 && ok*ok==n)return true; return false; } int main(){ long long L,R; cin>>L>>R; vector<long long> A(R-L+1); rep(i,A.size())A[i] = L+i; vector<long long> B = A; vector<bool> t(A.size(),false); for(long long i=2;i<=1000005;i++){ long long te = (L+i-1)/i; te *= i; for(long long j=te;j<=R;j+=i){ if(A[j-L]%(i*i)==0)t[j-L] = true; while(B[j-L]%i==0)B[j-L]/=i; } } int ans = 0; rep(i,B.size()){ if(t[i])continue; if(check(B[i]))continue; ans++; } cout<<ans<<endl; return 0; }