HackerRank Number Theory – Akhil and GF

Challenge: Akhil and GF

Subdomeniu: Number Theory (number-theory)

Scor cont: 40.0 / 40

Submission status: Accepted

Submission score: 1.0

Submission ID: 464734133

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/akhil-and-gf/problem

Cerinta

After dating for a long time, Akhil is finally going to propose to his girlfriend. She is very strong in mathematics, and will accept his proposal, if and only if Akhil solves a problem given by her. The problem is given below. Help Akhil solve it.

Akhil is given two numbers N and M, and he has to tell her the remainder when $111\cdots \text{(N times)}$ is divided by $M$.  

**Input Format**  
The first line contains an integer $T$ i.e. the number of test cases.  
Each of the next $T$ lines contain two space separated integers, $N$ and $M$.  

**Output Format**  
$T$ lines each containing ouptut for the corresponding test case. 

**Constraints**  
$1 \le T \le 10001$  
$1 \le N \le 10^{16}$  
$2 \le M \le 10^9$  

**Sample Input 00**  

	3
	3 3
	4 7
	5 18
    
**Sample Output 00**  

	0
	5	
	5
    
**Explanation** 

  111 % 3  = 0  
  1111 % 7 = 5  
  11111%18 = 5

Cod sursa

//akhil-and-gf.cpp
//Akhil and GF
//Ad Infinitum - Math Programming Contest August'14
//Author: derekhh

#include<iostream>
using namespace std;

long long mod_mul(long long x, long long y, long long n)
{
	if (!x) return 0;
	return (((x & 1)*y) % n + (mod_mul(x >> 1, y, n) << 1) % n) % n;
}

long long ModExp(long long a, long long b, long long n)
{
	long long c = 1, d = a;
	while (b)
	{
		if (b & 1) c = mod_mul(c, d, n);
		d = mod_mul(d, d, n);
		b >>= 1;
	}
	return c;
}

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		long long n, m;
		cin >> n >> m;
		long long tmp = ModExp(10, n, 9 * m);
		tmp--;
		if (tmp < 0) tmp += 9 * m;
		tmp /= 9;
		cout << tmp << endl;
	}
	return 0;
}