159. SelfReplicating Numbers
time limit per test: 0.5
sec.
memory limit per test: 65536
KB
input: standard input
output: standard output
Vasya's younger brother Misha is fond of playing with numbers. Two days ago he discovered that 9376^2 = 87909376  the last four digits constitute 9376 again. He called such numbers selfreplicating.
More precisely, an ndigit number is called selfreplicating if it is equal to the number formed by the last n digits of its square. Now Misha often asks Vasya to help him to find new such numbers. To make the things worse, Vasya's brother already knows what the scales of notation are, so he asks Vasya to find, for example, hexadecimal or binary selfreplicating numbers.
Vasya wants to help his brother, but unfortunately he is very busy now: he is seriously preparing and training for the next ACM Regional Contest. So he asked you to write a program that for a given base b and length n will find all ndigit selfreplicating numbers in the scale of notation with base b.
Input
The only line of the input contains two integer numbers b and n separated by a single space, the base b of the scale of notation (2 <= b <= 36) and the required length n (1 <= n <= 2000).
Output
The first line of the output contains K  the total number of selfreplicating numbers of length n in base b. Next K lines contain one ndigit number in base b each. Uppercase Latin letters from A to Z must be used to represent digits from 10 to 35. The selfreplicating numbers can be listed in arbitrary order.
Sample test(s)
Input
Sample input #1
10 4
Sample input #2
12 6
Output
Sample output #1
1
9376
Sample output #2
2
1B3854
A08369
Note
You can download pdf version of this task
here
Author:  Nikolay Durov

Resource:  ACM ICPC 20022003 NEERC, Northern Subregion

Date:  November, 2002

Server time: 20180219 01:05:35  Online Contester Team © 2002  2016. All rights reserved. 

