Soluție HackerRank pentru Akhil and GF, subdomeniul Number Theory, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Akhil and GF
- Domeniu: Number Theory
- Limbaj: C++14
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
Cerință
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·s 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 ≤ T ≤ 10001
1 ≤ N ≤ 10^16
2 ≤ M ≤ 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 sursă
//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;
}