結果

問題 No.2046 Ans Mod? Mod Ans!
ユーザー merlinmerlin
提出日時 2022-08-19 22:39:35
言語 Java21
(openjdk 21)
結果
AC  
実行時間 491 ms / 4,000 ms
コード長 1,643 bytes
コンパイル時間 3,005 ms
コンパイル使用メモリ 77,276 KB
実行使用メモリ 58,708 KB
最終ジャッジ日時 2024-05-09 17:27:20
合計ジャッジ時間 9,971 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 257 ms
41,836 KB
testcase_01 AC 255 ms
41,596 KB
testcase_02 AC 252 ms
41,704 KB
testcase_03 AC 259 ms
41,672 KB
testcase_04 AC 255 ms
41,816 KB
testcase_05 AC 260 ms
41,968 KB
testcase_06 AC 258 ms
41,656 KB
testcase_07 AC 251 ms
41,748 KB
testcase_08 AC 262 ms
42,004 KB
testcase_09 AC 279 ms
42,120 KB
testcase_10 AC 276 ms
42,068 KB
testcase_11 AC 291 ms
43,360 KB
testcase_12 AC 282 ms
42,760 KB
testcase_13 AC 395 ms
48,820 KB
testcase_14 AC 387 ms
49,096 KB
testcase_15 AC 411 ms
50,724 KB
testcase_16 AC 414 ms
51,324 KB
testcase_17 AC 403 ms
51,800 KB
testcase_18 AC 411 ms
52,076 KB
testcase_19 AC 405 ms
52,224 KB
testcase_20 AC 491 ms
58,708 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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;
    }
}
0