結果

問題 No.2046 Ans Mod? Mod Ans!
コンテスト
ユーザー merlin
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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