I think that this problem can be solved using binary search. If a number X is divisible by M, then X = F * M. And we can binary search this F.

   int l = 1, r = N / M + 1;
   int n_cnt = cnt(N);
   while(l < r){
      int mid = (r + l) / 2;
      if(cnt(mid * M) == n_cnt)
         r = mid;
      else
         l = mid + 1;
   }

In function cnt we just count amount of digits in our number like this:

int cnt(int x){
   int cnt = 0;
   while(x != 0)
      x /= 10, cnt ++;
   return cnt;
}

Let's say number of digits in N is x therefore you have to find smallest multiple of M which is greater than 10^(x-1). Let's call the number to be multiplied as K and number of digits in M as y. If M is perfect power of 10 then K will be 10^(x-y)(i.e if N = 100, M=10, K = 10), otherwise K will have (x-y) digits(i.e if N = 100(=10^2), M = 5(=5x10^0) then K = 20 which has 2 digits). Now as you know number of digits in K, now start from most significant digit and for each digit position i find largest number which when multiplied with M gives number smaller than 10^(x-1) and set that value there. Then finally add 1 to K to get the number just greater than 10^(x-1) as number K which we had found gives multiple just less than 10^(x-1). code to multiply strings https://www.geeksforgeeks.org/multiply-large-numbers-represented-as-strings/

The problem can be reduced to knapsack mod $$$M$$$ : define $$$dp_{i,j}$$$ as the minimal number of digits to change, knowing that first $$$i$$$ digits of $$$X$$$ are fixed, and that the current value of $$$X \bmod M$$$ is $$$j$$$.

Let $$$D \leq 100$$$ the number of digits in $$$N$$$. There will be $$$O(D \cdot M)$$$ states and $$$10$$$ transitions. Reconstruction of $$$X$$$ is easy. Final number of operations will be around $$$10^9$$$, my code works in less than 200ms on custom invocation of Codeforces (optimize cache usage, don't use long long, substract instead of using modulo operator).