結果
問題 | No.1653 Squarefree |
ユーザー | merlin |
提出日時 | 2021-08-20 23:38:53 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,757 bytes |
コンパイル時間 | 1,621 ms |
コンパイル使用メモリ | 166,280 KB |
実行使用メモリ | 159,308 KB |
最終ジャッジ日時 | 2024-04-22 08:29:43 |
合計ジャッジ時間 | 54,689 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,756 ms
158,412 KB |
testcase_01 | AC | 2 ms
7,752 KB |
testcase_02 | AC | 2 ms
7,624 KB |
testcase_03 | AC | 2 ms
7,624 KB |
testcase_04 | AC | 2 ms
7,624 KB |
testcase_05 | WA | - |
testcase_06 | AC | 2 ms
7,628 KB |
testcase_07 | WA | - |
testcase_08 | AC | 2 ms
7,628 KB |
testcase_09 | AC | 3 ms
7,752 KB |
testcase_10 | AC | 3 ms
7,624 KB |
testcase_11 | AC | 2 ms
7,624 KB |
testcase_12 | AC | 3 ms
7,752 KB |
testcase_13 | AC | 1,756 ms
159,180 KB |
testcase_14 | AC | 1,792 ms
159,044 KB |
testcase_15 | AC | 1,781 ms
159,048 KB |
testcase_16 | AC | 1,786 ms
158,796 KB |
testcase_17 | AC | 1,764 ms
158,920 KB |
testcase_18 | AC | 1,739 ms
158,792 KB |
testcase_19 | AC | 1,753 ms
158,920 KB |
testcase_20 | AC | 1,757 ms
159,180 KB |
testcase_21 | AC | 1,752 ms
159,176 KB |
testcase_22 | AC | 1,778 ms
159,304 KB |
testcase_23 | AC | 1,735 ms
159,048 KB |
testcase_24 | AC | 1,673 ms
158,024 KB |
testcase_25 | AC | 1,734 ms
158,792 KB |
testcase_26 | AC | 1,707 ms
159,172 KB |
testcase_27 | AC | 1,739 ms
158,668 KB |
testcase_28 | AC | 1,552 ms
147,524 KB |
testcase_29 | AC | 1,722 ms
159,052 KB |
testcase_30 | AC | 1,714 ms
159,048 KB |
testcase_31 | AC | 1,710 ms
159,176 KB |
testcase_32 | AC | 1,762 ms
159,176 KB |
testcase_33 | AC | 1,700 ms
159,176 KB |
testcase_34 | AC | 1,710 ms
159,308 KB |
testcase_35 | AC | 1,734 ms
159,048 KB |
testcase_36 | AC | 1,717 ms
159,044 KB |
testcase_37 | AC | 1,683 ms
158,660 KB |
testcase_38 | AC | 1,717 ms
158,796 KB |
testcase_39 | AC | 1,744 ms
158,796 KB |
testcase_40 | AC | 1,708 ms
158,920 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long int ll; const int N=17705360; bool p[N]; int mob[N],mlist[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) { 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-=1LL*(root/j-root/(j+1))*mlist[j]; for(j=2;j<=sqd;j++) if(root/j<=d) cur-=mlist[root/j]; else cur-=mxi[imax-j*j*i-1]; mxi.push_back(cur); sum+=cur; } return sum-(imax-1)*mlist[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); mobius(d); ll s1=0,s2=0; int i; for(i=1;i<=d;i++) { s1+=(b/(1LL*i*i))*mob[i]; if(i<=d2) s2+=(a/(1LL*i*i))*mob[i]; } mlist[0]=0; for(i=1;i<=d;i++) mlist[i]=mlist[i-1]+mob[i]; s1+=squarefree(b,imax,d); s2+=squarefree(a,ima,d2); cout<<(s1-s2)<<"\n"; return 0; }