[Trick] Checking Divisibility of Large Numbers by 2^a 5^b

Checking Divisibility of Large Numbers by 2^a * 5^b Just wanted to share a simple math trick regarding the divisibility of large numbers (represented as strings) when the divisor $$$N$$$ consists of powers of 2 and 5.

Core Idea

Since base 10 is formed by $$$10 = 2 \times 5$$$, any power $$$10^k$$$ contains $$$2^k \cdot 5^k$$$ as factors.

If $$$N = 2^a \cdot 5^b$$$ and $$$k = \max(a, b)$$$, then $$$10^k$$$ is guaranteed to be a multiple of $$$N$$$.

Any large integer $$$S$$$ can be written as:

$$$S = A \cdot 10^k + B$$$

where $$$B$$$ is the integer formed by the last $$$k$$$ digits of $$$S$$$, and $$$A$$$ represents all preceding digits.

Taking both sides modulo $$$N$$$:

$$$S \pmod N \equiv (A \cdot 10^k + B) \pmod N \equiv B \pmod N$$$

Takeaway: A number $$$S$$$ is divisible by $$$N = 2^a \cdot 5^b$$$ if and only if the integer formed by its last $$$k = \max(a, b)$$$ digits is divisible by $$$N$$$.

Quick Examples

$$$N = 8 = 2^3$$$: Check the last 3 digits ($$$k = 3$$$).
$$$N = 25 = 5^2$$$: Check the last 2 digits ($$$k = 2$$$).
$$$N = 200 = 2^3 \cdot 5^2$$$: Check the last 3 digits ($$$k = \max(3, 2) = 3$$$).

(Note: If $$$|S| \lt k$$$, simply evaluate the whole string).

C++ Implementation

Click to view C++ Solution

#include <iostream>
#include <string>
#include <algorithm>

using namespace namespace std;

// Checks if string S is divisible by N = (2^a) * (5^b)
bool isDivisible(const string &s, long long N, int a, int b) {
    int k = max(a, b);
    int len = s.length();
    
    // Extract at most the last k digits
    int start_idx = max(0, len - k);
    long long last_k_val = stoll(s.substr(start_idx));
    
    return (last_k_val % N == 0);
}

Practice Problems :