Problem setter : serius_white
Problem tester: maazbinasad3
Editorialist: serius_white
Difficulty:
Easy-Medium
Prerequisites :
Basic bit knowledge (not necessary) , can be solved without using bits (bits give a fancy, faster solution)
Explanation:
Quick analysis shows that fghij can only range from 01234 to 98765 which is at most
≈ 100K possibilities. An even better bound for fghij is the range 01234 to 98765 / N,
which has at most ≈ 50K possibilities for N = 2 and becomes smaller with increasing N. For
each attempted fghij, we can get abcde from fghij * N and then check if all 10 digits are
different. This is a doubly-nested loop with a time complexity of at most ≈ 50K×10 = 500K
operations per test case. This is small. The code shown below prints all such pairs, but you just need to count them.
Pseudo-code
for (int fghij = 1234; fghij <= 98765 / N; fghij++) {
int abcde = fghij * N; // this way, abcde and fghij are at most 5 digits
int tmp, used = (fghij < 10000); // if digit f=0, then we have to flag it
tmp = abcde; while (tmp) { used |= 1 << (tmp % 10); tmp /= 10; }
tmp = fghij; while (tmp) { used |= 1 << (tmp % 10); tmp /= 10; }
if (used == (1<<10) - 1) // if all digits are used, print it
printf("%0.5d / %0.5d = %d\n", abcde, fghij, N);
}