Now that Christmas is over, it is time for Santa to pay his elves. Santa has stored an unlimited amount of money inside his personal vault, and he heads over to his ATM to withdraw money for his elves.
Unfortunately, Santa’s arch nemesis, Klanta Sauce, has tampered with the keys of the ATM. Now the only number key that is working is ‘1’. This means Santa can only withdraw m dollars, where m is any number that consists of only ones when written in decimal.
Santa always withdraws an amount of money that can be evenly divided between his elves. He enjoys being generous, so he is willing to pay the elves as much money as needed. He is also very patient, so he is willing to press the ‘1’ key up to (2^31 – 1) times.
Help Santa find out if it is possible to withdraw an amount of money that can be evenly divided between the elves, and if it is, how many times he needs to press the ‘1’ key.
- LCM Cardinality (UVA 10892)