C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
int m, n, k, c; //use global variables to access num in functions
bool valid;
int cpos = 0; //point to the positon where the indexes of (k - c) numbers
int a[10]; //store the nums need to be enumerated in reversed order
//so, during dfs, a[0] will stroe the last num of k-c digits, a[cpos-1] will store the first
vector<int> div_prime(int n)
{
vector<int> prime_factors;
for (int i = 2; i <= n / i; i++ ) {
if (n % i == 0) {
prime_factors.push_back(i);
while (n % i == 0) n /= i;
}
}
if (n > 1) prime_factors.push_back(n);
return prime_factors;
}
void dfs(int x, int sum, vector<PII>& matches)
{
//cut branches
if ((k - x) * 9 + sum < m) return; //fill all 9 still can't match
if (x > k) return;
if (sum > m) return; //current sum is already invalid
//recursion ended
if (x == k and sum == m and a[0] != 9 and a[cpos - 1] != 0) { //last digit != 0, and first digit != 0
valid = true;
int res_num = 0;
//Qin Jiushao algorithm, get original num stored in digits in 10 radix
//a[] is stored in reversed order
for (int i = cpos - 1; i >= 0; i-- ) res_num = res_num * 10 + a[i];
//rest x digits in natural order
for (int i = 0; i < c; i++ ) res_num = res_num * 10 + 9;
matches.push_back({n, res_num});
return;
}
for (int i = 0; i <= 9; i++ ) {
a[cpos++] = i; //set current num to i
dfs(x + 1, sum + i, matches); //dfs next position
cpos--; //this pos may set other number, backdate
}
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int N; cin >> N;
for (int round = 1; round <= N; round++ ) {
if (round > 1) cout << endl;
valid = false; //new round, refresh
cin >> k >> m;
cout << "Case " << round << endl;
vector<int> p = div_prime(m); //do div prime factors on m
if (p.back() > 2) { //m exist primes > 2
vector<PII> matches;
for (int i = 0; i < p.size(); i++ ) {
if (p[i] == 2) continue; //we want gcd(m, n) > 2 and be prime
for (n = p[i]; n < m; n += p[i]) { //traverse all possible n
if ((m - n - 8) % 9 == 0) {
//the num must ended with ...9 or ...99 or ...999, otherwise n=m+1, gcd(n,m)<2
//(c-1) = (m-n-8)/9
//c means there are c nums of '9' in the last part
c = (m - n - 8) / 9 + 1;
dfs(c, c * 9, matches);
}
}
}
//sort by ascending n, if same n then sort actucl number
sort(matches.begin(), matches.end());
for (int i = 0; i < matches.size(); i++ ) {
if (i) cout << endl;
cout << matches[i].first << " " << matches[i].second;
}
}
else {
valid = false;
}
//be careful! no point here.
if (!valid) cout << "No Solution";
}
return 0;
}