結果
問題 | No.1653 Squarefree |
ユーザー | merlin |
提出日時 | 2021-08-20 23:43:05 |
言語 | Java21 (openjdk 21) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,427 bytes |
コンパイル時間 | 2,448 ms |
コンパイル使用メモリ | 87,944 KB |
実行使用メモリ | 127,528 KB |
最終ジャッジ日時 | 2024-10-14 08:53:39 |
合計ジャッジ時間 | 77,066 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | AC | 72 ms
37,972 KB |
testcase_02 | AC | 70 ms
38,152 KB |
testcase_03 | AC | 73 ms
37,660 KB |
testcase_04 | AC | 68 ms
37,776 KB |
testcase_05 | AC | 69 ms
37,672 KB |
testcase_06 | AC | 72 ms
37,960 KB |
testcase_07 | AC | 69 ms
37,680 KB |
testcase_08 | AC | 73 ms
38,000 KB |
testcase_09 | AC | 73 ms
38,036 KB |
testcase_10 | AC | 73 ms
38,160 KB |
testcase_11 | AC | 73 ms
37,804 KB |
testcase_12 | AC | 73 ms
37,660 KB |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | TLE | - |
testcase_19 | TLE | - |
testcase_20 | TLE | - |
testcase_21 | TLE | - |
testcase_22 | TLE | - |
testcase_23 | TLE | - |
testcase_24 | TLE | - |
testcase_25 | TLE | - |
testcase_26 | TLE | - |
testcase_27 | TLE | - |
testcase_28 | TLE | - |
testcase_29 | TLE | - |
testcase_30 | TLE | - |
testcase_31 | TLE | - |
testcase_32 | TLE | - |
testcase_33 | TLE | - |
testcase_34 | TLE | - |
testcase_35 | TLE | - |
testcase_36 | TLE | - |
testcase_37 | TLE | - |
testcase_38 | TLE | - |
testcase_39 | TLE | - |
testcase_40 | TLE | - |
ソースコード
import java.io.*; import java.util.*; class Main { public static void main(String args[])throws Exception { BufferedReader bu=new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb=new StringBuilder(); String s[]=bu.readLine().split(" "); long a=Long.parseLong(s[0])-1,b=Long.parseLong(s[1]); int imax=maxpower(b,5),ima=maxpower(a,5); int d=maxpower(b/imax,2),d2=maxpower(a/ima,2); if(a==0) d2=0; int dm=Math.max(d,d2),m[]=mobius(dm); long s1=0,s2=0; int i; for(i=1;i<=dm;i++) { if(i<=d) s1+=m[i]*(b/(1l*i*i)); if(i<=d2) s2+=m[i]*(a/(1l*i*i)); } m[0]=0; for(i=1;i<=dm;i++) m[i]+=m[i-1]; s1+=squarefree(b,imax,d,m); s2+=squarefree(a,ima,d2,m); sb.append(s1-s2+"\n"); System.out.print(sb); } static int maxpower(long 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; long v=1; for(i=0;i<p;i++) v*=m; if(v<=n) { ans=m; l=m+1; } else r=m-1; } return ans; } static int[] mobius(int n) { boolean p[]=new boolean[n+1]; int i,j,mob[]=new int[n+1]; Arrays.fill(mob,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; } long sq=1l*i*i; for(j=1;j<=n/sq;j++) mob[j*i*i]=0; } return mob; } //https://smsxgz.github.io/post/pe/counting_square_free_numbers/ static int squarefree(long n,int imax,int d,int mlist[]) { if(d==0) return 0; ArrayList<Integer> mxi=new ArrayList<>(); int sum=0; int 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))*mlist[j]; for(j=2;j<=sqd;j++) if(root/j<=d) cur-=mlist[(root/j)]; else cur-=mxi.get((imax-j*j*i-1)); mxi.add(cur); sum+=cur; } return sum-(imax-1)*mlist[d]; } }