結果

問題 No.2046 Ans Mod? Mod Ans!
ユーザー merlinmerlin
提出日時 2022-08-19 22:39:35
言語 Java21
(openjdk 21)
結果
AC  
実行時間 476 ms / 4,000 ms
コード長 1,643 bytes
コンパイル時間 2,885 ms
コンパイル使用メモリ 74,196 KB
実行使用メモリ 70,508 KB
最終ジャッジ日時 2023-08-22 11:45:36
合計ジャッジ時間 10,161 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 237 ms
54,168 KB
testcase_01 AC 229 ms
54,432 KB
testcase_02 AC 228 ms
54,828 KB
testcase_03 AC 241 ms
54,656 KB
testcase_04 AC 245 ms
54,484 KB
testcase_05 AC 236 ms
53,956 KB
testcase_06 AC 244 ms
54,552 KB
testcase_07 AC 242 ms
54,460 KB
testcase_08 AC 259 ms
54,576 KB
testcase_09 AC 264 ms
54,384 KB
testcase_10 AC 267 ms
54,532 KB
testcase_11 AC 271 ms
54,892 KB
testcase_12 AC 280 ms
54,508 KB
testcase_13 AC 393 ms
60,484 KB
testcase_14 AC 353 ms
59,808 KB
testcase_15 AC 389 ms
63,244 KB
testcase_16 AC 410 ms
62,396 KB
testcase_17 AC 395 ms
62,240 KB
testcase_18 AC 388 ms
62,148 KB
testcase_19 AC 404 ms
62,936 KB
testcase_20 AC 476 ms
70,508 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