poj3635java题解

POJ 3635 是一道比较经典的数学题目，主要考察了一些数学知识和算法。下面是这道题的 Java 解题思路和代码实现：

题目描述：

给定一个正整数N，求最小的正整数M，使得 N*M 的十进制表示中只包含数字0和1。

输入格式：

一个正整数N。

输出格式：

一个正整数M，表示满足条件的最小正整数M。

Java 代码实现：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long res = 1;
        Queue<Long> queue = new LinkedList<>();
        Set<Long> set = new HashSet<>();
        queue.offer(1L);
        set.add(1L);
        while (!queue.isEmpty()) {
            long t = queue.poll();
            if (t % n == 0) {
                res = t;
                break;
            }
            long a = (t * 10) % n;
            long b = (t * 10 + 1) % n;
            if (!set.contains(a)) {
                queue.offer(a);
                set.add(a);
            }
            if (!set.contains(b)) {
                queue.offer(b);
                set.add(b);
            }
        }
        System.out.println(res);
    }
}

思路解析：

这道题的解题思路比较巧妙，我们可以采用 BFS 算法来解决。我们可以从 1 开始进行 BFS，每次将当前的数乘以 10 或者乘以 10 再加上 1，得到两个新的数，然后判断这两个新的数是否是 n 的倍数，如果是，则找到了最小的满足条件的数，退出 BFS。如果不是，则将两个新的数加入队列，继续进行 BFS。需要注意的是，由于 N 可能非常大，所以我们需要使用 long 类型来存储数值，同时我们需要使用集合来避免重复计算。