fork(3) download
copy 
  1. /**
  2.  * Kelas untuk menghitung jumlah setiap elemen dalam sebuah deret aritmatik. Metode
  3.  * yang dipakai adalah metode Gauss ditambah dengan prinsip Inklusi-Ekslusi.
  4.  */
  5. class Gauss {
  6. 	/**
  7. 	 * Fungsi untuk menjumlahkan semua bilangan kelipatan a1, a2, a3 ... an dari
  8. 	 * 1 sampai limit (inclusive). Sebagai contoh: Jumlah bilangan kelipatan 2 dan 3
  9. 	 * dari 1 sampai 100 adalah sum(new long[]{2L, 3L}, 0, 2, 100L).
  10. 	 * 
  11. 	 * Bagian terkeren dari fungsi ini : ga ada if! Kekekekekek
  12. 	 * 
  13. 	 * @param numbers array dari bilangan-bilangan yang diinginkan. Asumsi : array
  14. 	 * tidak null. Asumsi : setiap bilangan koprima (FPB-nya 1) dengan bilangan
  15. 	 * lainnya.
  16. 	 * 
  17. 	 * @param lower batas bawah dari array. Asumsi : lower berada di dalam rentang
  18. 	 * yang diperbolehkan : 0 s/d numbers.length - 1
  19. 	 * 
  20. 	 * @param length panjang array. Asumsi : lower + length <= numbers.length
  21. 	 * 
  22. 	 * @param limit batas maksimal deret (inclusive). Asumsi : limit adalah bilangan
  23. 	 * bulat tidak negatif.
  24. 	 * 
  25. 	 * @return jumlah bilangan kelipatan a1, a2, a3 ... an dari 1 sampai limit
  26. 	 */
  27. 	public long sum(long[] numbers, int lower, int length, long limit){
  28. 		assert(numbers != null);
  29. 		// Siaga 2 : Pemeriksaan asumsi fpb(ai, aj) = 1 tidak dilakukan!!
  30. 		assert(lower >= 0 && lower < numbers.length);
  31. 		assert(lower + length <= numbers.length);
  32. 		assert(limit >= 0L);
  33.  
  34. 		// Menghitung ukuran array : 2^length - 1
  35. 		// Siaga 1 : Arithmetic Overflow!
  36. 		// Siaga 1 : Out of memory!
  37. 		int size = (1 << length) - 1;
  38.  
  39. 		// Deklarasi array
  40. 		long[] ar = new long[size];
  41.  
  42. 		// Inisialisasi setiap elemen pada array dengan -1
  43. 		for (int i = 0; i < size; i++) ar[i] = -1L;
  44.  
  45. 		// Deklarasi & inisialisasi return value
  46.         long result = 0L;
  47.  
  48.         // Deklarasi & inisialisasi index array yang akan ditulisi
  49.         int idx = 0;
  50.  
  51.         // Deklarasi & inisialisasi batas atas/guard dari loop
  52.         int upper = lower + length;
  53.  
  54.         // Selama batas bawah masih belum 'bertemu' batas atas, lanjutkan iterasi
  55.         for (; lower < upper; lower++){
  56.             // Bilangan yang di-input
  57.             long number = numbers[lower];
  58.  
  59.             // Baca semua isi array yang sudah pernah ditulisi
  60.             // Jaga loop untuk tidak membaca elemen yang belum ditulis
  61.             for (int i = 0, j = idx; i < j; i++) {
  62.                 // Elemen berikut = -Bilangan yang diinput * isi array
  63.             	// Siaga 1 : Arithmetic Overflow!
  64.                 long element = -number * ar[i];
  65.  
  66.                 // Tulis elemen tersebut ke dalam array
  67.                 // Naikkan index
  68.                 ar[idx++] = element;
  69.  
  70.                 // Hitung jumlah
  71.                 // Tambahkan jumlah tersebut ke dalam hasil akhir
  72.                 result += calculate(limit, element);
  73.             }
  74.  
  75.             // Default : tulis bilangan yang di-input oleh user ke dalam array
  76.             // Naikkan index
  77.             ar[idx++] = number;
  78.  
  79.             // Hitung jumlah
  80.             // Tambahkan jumlah tersebut ke dalam hasil akhir
  81.             result += calculate(limit, number);
  82.         }
  83.  
  84.         return result;
  85.     }
  86.  
  87.     /**
  88.      * Fungsi untuk menghitung jumlah semua bilangan kelipatan 'number' dari 1
  89.      * sampai 'limit' (inclusive). Sebagai contoh: Jumlah bilangan kelipatan 2 dari
  90.      * 1 sampai 100 dinyatakan sebagai calculate(2, 100) = 2550
  91.      * 
  92.      * Bagian terkeren dari fungsi ini : mampu menerima 'number' positif ataupun
  93.      * negatif! xixixi
  94.      * 
  95.      * @param limit batas maksimal deret yang ingin dihitung (inclusive). Asumsi :
  96.      * limit adalah bilangan bulat tidak negatif
  97.      * 
  98.      * @param number kelipatan bilangan yang ingin dihitung. Asumsi : number adalah
  99.      * bilangan bulat tidak 0
  100.      * 
  101.      * @return jumlah semua bilangan kelipatan number dari 1...limit
  102.      */
  103. 	public long calculate(long limit, long number){
  104. 		assert(limit >= 0L);
  105. 		assert(number != 0L);
  106.  
  107.         // Menghitung banyaknya elemen
  108.         long count = limit / number;
  109.  
  110.         // Banyaknya elemen selalu positif
  111.         if (count < 0) count = -count;
  112.  
  113.         // Jika ada elemen yang dimaksud maka akan dihitung.
  114.         // Jika tidak ada berarti 0
  115.         if (count > 0)
  116.             // S(n) = 1/2 * banyaknya elemen * (elemen pertama + elemen terakhir)
  117.         	// Siaga 1 : Arithmetic Overflow!
  118.             return number * (count + 1L) * count / 2L;
  119.         else
  120.             return 0L;
  121.     }
  122.  
  123.  
  124.     /**
  125.     	main method - test case
  126.     */
  127.     public static void main (String... args){
  128.     	Gauss g = new Gauss();
  129.     	long before, after, ellapsed;
  130.     	long result;
  131.  
  132.     	before = System.currentTimeMillis();
  133.     	result = g.sum(new long[]{2L, 3L, 5L, 7L, 11L, 13L}, 0, 6, 999999L);
  134.     	after = System.currentTimeMillis();
  135.     	ellapsed = after - before;
  136.     	System.out.println(result + " dalam " + ellapsed + " ms");
  137.  
  138.     	before = System.currentTimeMillis();
  139.     	result = g.sum(new long[]{2L, 3L, 5L, 7L, 11L, 13L}, 0, 6, 9999999L);
  140.     	after = System.currentTimeMillis();
  141.     	ellapsed = after - before;
  142.     	System.out.println(result + " dalam " + ellapsed + " ms");
  143.  
  144.     	before = System.currentTimeMillis();
  145.     	result = g.sum(new long[]{2L, 3L, 5L, 7L, 11L, 13L}, 0, 6, 99999999L);
  146.     	after = System.currentTimeMillis();
  147.     	ellapsed = after - before;
  148.     	System.out.println(result + " dalam " + ellapsed + " ms");
  149.  
  150.     	before = System.currentTimeMillis();
  151.     	result = g.sum(new long[]{2L, 3L, 5L, 7L, 11L, 13L}, 0, 6, 999999999L);
  152.     	after = System.currentTimeMillis();
  153.     	ellapsed = after - before;
  154.     	System.out.println(result + " dalam " + ellapsed + " ms");
  155.  
  156.     	before = System.currentTimeMillis();
  157.     	result = g.sum(new long[]{2L, 3L, 5L, 7L, 11L, 13L, 17L}, 0, 7, 999999L);
  158.     	after = System.currentTimeMillis();
  159.     	ellapsed = after - before;
  160.     	System.out.println(result + " dalam " + ellapsed + " ms");
  161.  
  162.     	before = System.currentTimeMillis();
  163.     	result = g.sum(new long[]{2L, 3L, 5L, 7L, 11L, 13L, 17L}, 0, 7, 9999999L);
  164.     	after = System.currentTimeMillis();
  165.     	ellapsed = after - before;
  166.     	System.out.println(result + " dalam " + ellapsed + " ms");
  167.  
  168.     	before = System.currentTimeMillis();
  169.     	result = g.sum(new long[]{2L, 3L, 5L, 7L, 11L, 13L, 17L}, 0, 7, 99999999L);
  170.     	after = System.currentTimeMillis();
  171.     	ellapsed = after - before;
  172.     	System.out.println(result + " dalam " + ellapsed + " ms");
  173.  
  174.     	before = System.currentTimeMillis();
  175.     	result = g.sum(new long[]{2L, 3L, 5L, 7L, 11L, 13L, 17L}, 0, 7, 999999999L);
  176.     	after = System.currentTimeMillis();
  177.     	ellapsed = after - before;
  178.     	System.out.println(result + " dalam " + ellapsed + " ms");
  179.  
  180.     	before = System.currentTimeMillis();
  181.     	result = g.sum(new long[]{2L, 3L, 5L, 7L, 11L, 13L, 17L, 19L}, 0, 8, 999999L);
  182.     	after = System.currentTimeMillis();
  183.     	ellapsed = after - before;
  184.     	System.out.println(result + " dalam " + ellapsed + " ms");
  185.  
  186.     	before = System.currentTimeMillis();
  187.     	result = g.sum(new long[]{2L, 3L, 5L, 7L, 11L, 13L, 17L, 19L}, 0, 8, 9999999L);
  188.     	after = System.currentTimeMillis();
  189.     	ellapsed = after - before;
  190.     	System.out.println(result + " dalam " + ellapsed + " ms");
  191.  
  192.     	before = System.currentTimeMillis();
  193.     	result = g.sum(new long[]{2L, 3L, 5L, 7L, 11L, 13L, 17L, 19L}, 0, 8, 99999999L);
  194.     	after = System.currentTimeMillis();
  195.     	ellapsed = after - before;
  196.     	System.out.println(result + " dalam " + ellapsed + " ms");
  197.  
  198.     	before = System.currentTimeMillis();
  199.     	result = g.sum(new long[]{2L, 3L, 5L, 7L, 11L, 13L, 17L, 19L}, 0, 8, 999999999L);
  200.     	after = System.currentTimeMillis();
  201.     	ellapsed = after - before;
  202.     	System.out.println(result + " dalam " + ellapsed + " ms");
  203.     }    
  204. }
Success #stdin #stdout 0.05s 213440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
404095596800 dalam 0 ms
40409594590409 dalam 0 ms
4040958909040980 dalam 0 ms
404095905404095610 dalam 0 ms
409738188044 dalam 0 ms
40973752813859 dalam 0 ms
4097373234996935 dalam 0 ms
409737322997982171 dalam 0 ms
414490217263 dalam 1 ms
41448855991592 dalam 0 ms
4144879962351863 dalam 0 ms
414487987708284041 dalam 0 ms
https://ideone.com/fDFPy
language:
Java (HotSpot 12)
created:
15 years 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!