Analisis Dan Penyelesaian Spoj 35631 – Moon Safari (Extreme) Menggunakan Algoritma Komputasi Numerik Pada Penerapan Kalkulus Finite Dan Ekstrapolasi Lagrange

Charles, Charles (2025) Analisis Dan Penyelesaian Spoj 35631 – Moon Safari (Extreme) Menggunakan Algoritma Komputasi Numerik Pada Penerapan Kalkulus Finite Dan Ekstrapolasi Lagrange. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025211082-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (2MB) | Request a copy

Abstract

Permasalahan yang diangkat pada tugas akhir ini adalah permasalahan SPOJ 35631 – MOON SAFARI (EXTREME). Pada studi kasus ini, diberikan nilai n, a, dan r yang dikomputasi menggunakan rumus penjumlahan yang diberikan dengan hasil akhir komputasi berupa hasil sisa bagi nilai akhir dengan 10^7. Rumus penjumlahan berupa sebagai berikut:
s(n,a,r)=∑_(i=1)^n▒〖a^i i^r 〗mod 10^7
Tugas akhir ini membahas mengenai permasalahan rumus komputasi s(n,a,r)=∑_(i=1)^n▒〖a^i i^r 〗 yang tidak bisa dilakukan secara looping biasa dikarenakan konstrain yang diberikan memiliki batas akhir 10^18 yang melewati batas limit waktu yang diberikan apabila menggunakan metode naif. Maka dari itu digunakan metode finite calculus untuk melakukan simplifikasi dari rumus komputasi yang sudah diberikan sehingga dapat menyelesaikan permasalahan dalam kompleksitas waktu =====================================================================================================================================
The problem raised in this final assignment is the SPOJ 35631 – MOON SAFARI (EXTREME) problem. In this case study, the values of n, a, and r are given which are computed using the summation formula given with the final computation result in the form of the remainder of the final value divided by 10^7. The summation formula is as follows:
s(n,a,r)=∑_(i=1)^n▒〖a^i i^r 〗mod 10^7
This undergraduate thesis discusses the problem of the computation formula s(n,a,r)=∑_(i=1)^n▒〖a^i i^r 〗which cannot be done by ordinary looping because the given constraint has a final limit of 10^18 which exceeds the time limit given when using the naive method. Therefore, the finite calculus method is used to simplify the given computational formula so that it can solve the problem in time complexity

Item Type:	Thesis (Other)
Uncontrolled Keywords:	fast modular exponentiation, finite calculus, lagrange, linear sieve
Subjects:	T Technology > T Technology (General) > T57.74 Linear programming
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Charles Charles
Date Deposited:	01 Jul 2025 03:30
Last Modified:	01 Jul 2025 03:30
URI:	http://repository.its.ac.id/id/eprint/119294

Actions (login required)

View Item