Using divide and conquer

Question

So, I have a problem.

The input consists of two numbers N and M. N basically tells us the number of 1 that will be present and M is the number, with which we divide and return the remainder.

1≤N≤10^16
2≤M≤10^9

Sample input:
3 3
4 7
5 18

Sample output:
0
5   
5

Explanation:

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

Time constraints: Upto 1 sec.

Since the input is very large, I obviously cannot use the modulo operator. I was thinking of bitwise operators but that too will not let me be withing the time limit. Any ideas? Thanks!

Answer 1

Okay NetVipeC's answer got ugly really fast

This answer is based on three identities

x(1) = 1
x(n) = x(n-1) * 10 + 1
x(2n) = x(n)*(x(n)*9 + 2)

These hold over Z_M as well.

I wrote those identities bottom up, but the implementation is top down since its so much simpler.

#include <stdio.h>

long long modulo(long long n, long long m) {
    if (n == 1) return 1;
    long long mod = modulo(n / 2, m);
    long long whole = ((mod * 9 + 2) * mod) % m;
    if(n & 1)
        return (whole * 10 + 1) % m;
    return whole;
}

int main() {
    printf("%ld\n", modulo(3, 3));
    printf("%ld\n", modulo(4, 7));
    printf("%ld\n", modulo(5, 18));
    printf("%ld\n", modulo(1e6, 123456789));
    printf("%ld\n", modulo(1e15, 123456789));
}

Output:

time ./tst
0
5
5
1239742
93889873
./tst  0.00s user 0.00s system 56% cpu 0.002 total