BFRAC - Editorial

editorial
, ,
1

PROBLEM LINK:

Contest

Author: Rahul Sharma

Tester: Sumukh Bhardwaj

Editorialist: Rahul Sharma

DIFFICULTY:

Easy

PREREQUISITES:

Basic programming, modulo, math

PROBLEM:

Given numerator Num and denominator Den of a fraction, a non-negative integer K and a positive integer N. A is given as decimal part of fraction of K length. You need to tell the value of A \mod N.

EXPLANATION:

We are interested in fractional part thus we start with
rem = Num \mod Den
sum = 0

To get first decimal digit
digit = (rem*10)/Den
rem = (rem*10) \mod Den

Since we want to take the modulo N of the decimal part we will use Modular Arithmetic to update the sum
sum = ((sum \mod N * 10 \mod N ) \mod N + digit \mod N) \mod N
This will ensure that we never overflow.
Repeating this K times will give the answer which will be present in sum

COMPLEXITIES:

Time Complexity: O(K) for each test case
Space Complexity: O(1) for each test case

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;

int main()
{
	long long int a, b, k, n, sum = 0, add = 0, rem;

	cin >> a >> b >> k >> n;

	rem = a % b;

	long long int i = 0;

	while(i < k)
	{
		add = (rem*10)/b;
		rem = (rem*10)%b;

		sum = ((sum % n)*(10 % n)%n + add % n) % n;
		i++;
	}

	cout << sum;
}