結果
問題 |
No.2046 Ans Mod? Mod Ans!
|
ユーザー |
![]() |
提出日時 | 2022-08-19 22:39:35 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 507 ms / 4,000 ms |
コード長 | 1,643 bytes |
コンパイル時間 | 3,549 ms |
コンパイル使用メモリ | 77,564 KB |
実行使用メモリ | 58,836 KB |
最終ジャッジ日時 | 2024-12-16 08:25:47 |
合計ジャッジ時間 | 10,212 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
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(); int n=Integer.parseInt(bu.readLine()); String s[]=bu.readLine().split(" "); /* a[i]%a[j]-a[j]%a[i]; consider a[i]<a[j], as a[i]=a[j] will yield 0 a[j]-k*a[i] will be a[j]%a[i] and a[i]%a[j] will be a[i] */ int N=200005; long sum[]=new long[N+1],c[]=new long[N+1]; int a,i; for(i=0;i<n;i++) { a=Integer.parseInt(s[i]); update(sum,a,a,N); update(c,a,1,N); } long ans=0; for(i=N;i>0;i--) { long here=query(c,i)-query(c,i-1); //how many i's are there in array int j=1; long aij=0,aji; while(j*i<=N) { long count=query(c,Math.min(j*i+i-1,N))-query(c,j*i-1); long tot=query(sum,Math.min(j*i+i-1,N))-query(sum,j*i-1); aij+=tot-count*i*j; j++; } aji=(query(c,N)-query(c,i))*i; ans+=Math.abs(aij-aji)*here; } System.out.println(ans); } static void update(long bit[],int i,int v,int n) { while(i<=n) { bit[i]+=v; i+=i&-i; } } static long query(long bit[],int i) { long s=0; while(i>0) { s+=bit[i]; i-=i&-i; } return s; } }