結果
問題 | No.1653 Squarefree |
ユーザー | merlin |
提出日時 | 2022-05-03 06:12:55 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,540 ms / 2,000 ms |
コード長 | 1,768 bytes |
コンパイル時間 | 1,434 ms |
コンパイル使用メモリ | 171,816 KB |
実行使用メモリ | 90,112 KB |
最終ジャッジ日時 | 2024-07-02 10:20:03 |
合計ジャッジ時間 | 29,384 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,479 ms
89,804 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 1,485 ms
89,976 KB |
testcase_14 | AC | 1,452 ms
89,940 KB |
testcase_15 | AC | 1,486 ms
90,108 KB |
testcase_16 | AC | 1,463 ms
89,920 KB |
testcase_17 | AC | 1,476 ms
89,948 KB |
testcase_18 | AC | 1,490 ms
90,036 KB |
testcase_19 | AC | 1,525 ms
89,904 KB |
testcase_20 | AC | 1,506 ms
90,112 KB |
testcase_21 | AC | 1,472 ms
89,980 KB |
testcase_22 | AC | 1,467 ms
89,980 KB |
testcase_23 | AC | 1,502 ms
90,100 KB |
testcase_24 | AC | 1,500 ms
89,748 KB |
testcase_25 | AC | 1,510 ms
89,928 KB |
testcase_26 | AC | 1,433 ms
89,984 KB |
testcase_27 | AC | 1,484 ms
89,920 KB |
testcase_28 | AC | 1,344 ms
87,464 KB |
testcase_29 | AC | 1,455 ms
89,944 KB |
testcase_30 | AC | 1,515 ms
89,980 KB |
testcase_31 | AC | 1,517 ms
89,980 KB |
testcase_32 | AC | 1,463 ms
89,984 KB |
testcase_33 | AC | 1,540 ms
89,980 KB |
testcase_34 | AC | 1,474 ms
90,112 KB |
testcase_35 | AC | 1,506 ms
90,104 KB |
testcase_36 | AC | 1,518 ms
89,940 KB |
testcase_37 | AC | 1,531 ms
89,900 KB |
testcase_38 | AC | 1,503 ms
89,980 KB |
testcase_39 | AC | 1,500 ms
89,896 KB |
testcase_40 | AC | 1,461 ms
89,904 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long int ll; const int N=17705360; bool p[N]; int mob[N]; void mobius(int n) { int i,j; for(i=0;i<=n;i++) {p[i]=false; mob[i]=1;} for(i=2;i<=n;i++) if(!p[i]) { mob[i]=-1; for(j=2;j<=n/i;j++) { p[i*j]=true; mob[i*j]*=-1; } ll sq=1LL*i*i; for(j=1;j<=n/sq;j++) mob[j*i*i]=0; } } int maxpower(ll n,int p) { if(n==0) return 1; int l=1,r=(int)1e9,m,ans,i; if(p==5) r=3190; ans=r; while(l<=r) { m=(l+r)>>1; ll v=1; for(i=0;i<p;i++) v*=m; if(v<=n) { ans=m; l=m+1; } else r=m-1; } return ans; } //https://smsxgz.github.io/post/pe/counting_square_free_numbers/ int squarefree(ll n,int imax,int d) { if(d==0) return 0; vector<int> mxi; int sum=0,i; for(i=imax-1;i>0;i--) { int cur=1; int root=maxpower(n/i,2),sqd=maxpower(root,2),j; for(j=1;j<=root/(sqd+1);j++) cur-=(root/j-root/(j+1))*mob[j]; for(j=2;j<=sqd;j++) if(root/j<=d) cur-=mob[root/j]; else cur-=mxi[imax-j*j*i-1]; mxi.push_back(cur); sum+=cur; } return sum-(imax-1)*mob[d]; } int main() { ll a,b; cin>>a>>b; a--; int imax=maxpower(b,5),ima=maxpower(a,5); int d=maxpower(b/imax,2),d2=maxpower(a/ima,2); int dm=max(d,d2); mobius(dm); ll s1=0,s2=0; int i; mob[0]=0; for(i=1;i<=dm;i++) { if(i<=d) s1+=(b/(1LL*i*i))*mob[i]; if(i<=d2) s2+=(a/(1LL*i*i))*mob[i]; mob[i]+=mob[i-1]; } s1+=squarefree(b,imax,d); s2+=squarefree(a,ima,d2); cout<<(s1-s2)<<"\n"; return 0; }