fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     static class Cell{
  6.         int x,y;
  7.         Cell(int x,int y){
  8.             this.x=x;
  9.             this.y=y;
  10.         }
  11.     }
  12.  
  13.     static final int MAX=1000000;
  14.     static final long MOD=1000000007L;
  15.  
  16.     static int[][] grid;
  17.     static int n,m;
  18.  
  19.     static int[][] comp;
  20.     static boolean[][] vis;
  21.  
  22.     static int[] dx={1,-1,0,0};
  23.     static int[] dy={0,0,1,-1};
  24.  
  25.     static ArrayList<ArrayList<Cell>> components=new ArrayList<>();
  26.  
  27.     static void bfs(int sx,int sy,int id){
  28.  
  29.         Queue<Cell> q=new LinkedList<>();
  30.  
  31.         q.add(new Cell(sx,sy));
  32.  
  33.         vis[sx][sy]=true;
  34.  
  35.         comp[sx][sy]=id;
  36.  
  37.         ArrayList<Cell> list=new ArrayList<>();
  38.  
  39.         while(!q.isEmpty()){
  40.  
  41.             Cell cur=q.poll();
  42.  
  43.             list.add(cur);
  44.  
  45.             for(int k=0;k<4;k++){
  46.  
  47.                 int nx=cur.x+dx[k];
  48.                 int ny=cur.y+dy[k];
  49.  
  50.                 if(nx>=0 && ny>=0 && nx<n && ny<m){
  51.  
  52.                     if(grid[nx][ny]>0 && !vis[nx][ny]){
  53.  
  54.                         vis[nx][ny]=true;
  55.  
  56.                         comp[nx][ny]=id;
  57.  
  58.                         q.add(new Cell(nx,ny));
  59.  
  60.                     }
  61.                 }
  62.             }
  63.  
  64.         }
  65.  
  66.         components.add(list);
  67.  
  68.     }
  69.  
  70.     public static void main(String[] args){
  71.  
  72.         Scanner sc=new Scanner(System.in);
  73.  
  74.         n=sc.nextInt();
  75.         m=sc.nextInt();
  76.  
  77.         grid=new int[n][m];
  78.  
  79.         comp=new int[n][m];
  80.  
  81.         vis=new boolean[n][m];
  82.  
  83.         HashMap<Integer,Integer> freq=new HashMap<>();
  84.  
  85.         for(int i=0;i<n;i++){
  86.  
  87.             for(int j=0;j<m;j++){
  88.  
  89.                 grid[i][j]=sc.nextInt();
  90.  
  91.                 if(grid[i][j]>0){
  92.  
  93.                     freq.put(grid[i][j],
  94.                             freq.getOrDefault(grid[i][j],0)+1);
  95.  
  96.                 }
  97.  
  98.             }
  99.  
  100.         }
  101.  
  102.         int id=0;
  103.  
  104.         for(int i=0;i<n;i++){
  105.  
  106.             for(int j=0;j<m;j++){
  107.  
  108.                 if(grid[i][j]>0 && !vis[i][j]){
  109.  
  110.                     bfs(i,j,id++);
  111.  
  112.                 }
  113.  
  114.             }
  115.  
  116.         }
  117.  
  118.         long finalAnswer=0;
  119.  
  120.         for(ArrayList<Cell> component:components){
  121.  
  122.             // Remove current component
  123.             for(Cell c:component){
  124.  
  125.                 int val=grid[c.x][c.y];
  126.  
  127.                 freq.put(val,freq.get(val)-1);
  128.  
  129.                 if(freq.get(val)==0)
  130.                     freq.remove(val);
  131.  
  132.             }
  133.  
  134.             // Calculate sed values
  135.             for(Cell c:component){
  136.  
  137.                 int val=grid[c.x][c.y];
  138.  
  139.                 long sed=0;
  140.  
  141.                 for(int multiple=val;
  142.                     multiple<=MAX;
  143.                     multiple+=val){
  144.  
  145.                     Integer f=freq.get(multiple);
  146.  
  147.                     if(f!=null){
  148.  
  149.                         sed += (long)multiple*f;
  150.  
  151.                     }
  152.  
  153.                 }
  154.  
  155.                 finalAnswer=(finalAnswer+sed)%MOD;
  156.  
  157.             }
  158.  
  159.             // Restore component
  160.             for(Cell c:component){
  161.  
  162.                 int val=grid[c.x][c.y];
  163.  
  164.                 freq.put(val,
  165.                         freq.getOrDefault(val,0)+1);
  166.  
  167.             }
  168.  
  169.         }
  170.  
  171.         System.out.println(finalAnswer%MOD);
  172.  
  173.     }
  174.  
  175. }
Success #stdin #stdout 0.22s 72908KB
comments (?)
stdin
copy 
2 2

2 -1
-1 4
stdout
copy 
4
https://ideone.com/Of8CF6
language:
Java (HotSpot 12)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!