Magic Number问题的分析

即将开学了，玩了差不多一个月，为了找找编程的感觉，所以从浙大ACM的网站上找了一些ACM题来练练手。虽然题已经过期了，不知道是否正确，但是能够提供一个思路。

本题地址：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=4757

题目：

若对于任意正整数x，把正整数y放在x的右边所构成的新整数z，总满足z mod y = 0，则y被称为“魔法数字（Magic Number）”。

输入：

输入为多条用例，每条用例包含两个正整数m, n（1<=m<=n<= 2^31-1），直至文件结束。

输出：

对于每条用例，输出m, n之间（包含m, n）的魔法数字的数目。

输入示例：

1 1

1 10

输出示例：

1

4

分析：

如题，z是形如<xy>的一个整数，转化为表达式为z = 10 ^ n * x + y，其中n为y的位数。

根据z mod y = 0，则10 ^ n * x + y mod y = 0，即y是10 ^ n * x +y的一个因数。

因此原命题与如下的命题等价：

对于任意的正整数x，存在非1正整数m，使等式10 ^ n * x + y = m * y成立，其中n为y的位数。

转化等式得：m = 10 ^ n * x / y + 1。

由于x的任意性，要使m作为非1正整数存在，则10 ^ n / y必须为正整数。

因此原命题与如下的命题等价：

若10 ^ n mod y = 0（n为正整数y的位数），则y为魔法数字。

下面是使用Java对本问题的实现：

package acm;import java.io.FileInputStream;import java.io.FileNotFoundException;import java.io.InputStream;import java.util.NoSuchElementException;import java.util.Scanner;public class MagicNumber {public static void main(String[] args) {InputStream is = null;Scanner in = null;try {is = new FileInputStream("E:/eclipse_workspace/JavaTest/tmp/test.txt");in = new Scanner(is);String line = null;while ((line = in.nextLine()) != null) {String[] s = line.split(" ");int m = Integer.parseInt(s[0]);int n = Integer.parseInt(s[1]);int count = 0;for (int i = m; i <= n; i++) {if (judge(i)) {count++;}}System.out.println(count);}} catch (FileNotFoundException e) {e.printStackTrace();} catch (NoSuchElementException e) {in.close();}}private static boolean judge(int y) {int n = 0;int tmp = y;while (tmp != 0) {tmp /= 10;n++;}if (Math.pow(10, n) % y == 0) {return true;} else {return false;}}}