数论——因子组合

╰+哭是因爲堅強的太久メ 2024-03-30 11:48 24阅读 0赞

## 数论——因子组合【幸运数字】 ##

`记录一道关于数论的题目，题目本身不难，主要是学习一下思想~`

--------------------

#### 文章目录 ####

*  数论——因子组合【幸运数字】
 *  题目
 *  常规思路or错误思路
 *  正确思路（一）
 *  总结

--------------------

## 题目 ##

> 到 X 星球旅行的游客都被发给一个整数，作为游客编号。X 星的国王有个怪癖，他只喜欢数字 3，5 和 7。  
> 国王规定，游客的编号如果只含有因子：3，5，7 就可以获得一份奖品。  
> 我们来看前 10 个幸运数字是：  
> 3 5 7 9 15 21 25 27 35 45 因而第 11 个幸运数字是： 49  
> 小明领到了一个幸运数字 59084709587505，他去领奖的时候，人家要求他准确地说出这是第几个幸运数字，否则领不到奖品。  
> 请你帮小明计算一下，59084709587505 是第几个幸运数字。

## 常规思路or错误思路 ##

首先来分析一下这道题：初次接触此类题的时候，我们通常会想到，先写一个方法——判断某个数的因子是否只含有3，5，7；于是乎，我们写了一个方法，这个方法也确实能够做出准确的判断，而在这个方法中，你或许还会用到一些集合，比如HashSet等…然后输入49，得出是第11个数。

> int类型代码如下（Java）：

import java.util.HashSet;
    
    public class Main{
        
        static HashSet<Integer> hashSet = new HashSet<>();
        public static void main(String[] args) {
        
    //        long num = 59084709587505L;
            int num = 49;
            int count = 2;
            while (3 * count < num) {
        
                hashSet.add(3 * count);
                count++;
            }
            count = 2;
            while (5 * count < num) {
        
                hashSet.add(5 * count);
                count++;
            }
            count = 2;
            while (7 * count < num) {
        
                hashSet.add(7 * count);
                count++;
            }
            count = 0;
            for (int i = 2; i <= num; i++) {
        
                if (judge(i))
                    count++;
            }
            System.out.println(count);
        }
    
        private static boolean judge(int num) {
        
            boolean flag = num % 3 == 0 || num % 5 == 0 || num % 7 == 0;
            for (int i = 2; i < num; i++) {
        
                if (i != 3 && i != 5 && i != 7 && !hashSet.contains(i))
                    if (num % i == 0) {
        
                        flag = false;
                        break;
                    }
            }
            return flag;
        }
    }

> BigInteger类型代码如下（Java）：

import java.math.BigInteger;
    import java.util.Arrays;
    import java.util.HashSet;
    
    public class demo04_BigInteger {
        
        public static void main(String[] args) {
        
            BigInteger num = new BigInteger("49");
            int count = 0;
            int i = 2;
            BigInteger temp = new BigInteger(String.valueOf(i));
            while (true) {
        
                if (temp.compareTo(num) <= 0) {
        
                    if (judge(temp)) {
        
                        count++;
                        System.out.print(temp+" ");
                    }
                    temp = new BigInteger(String.valueOf(++i));
                } else break;
            }
            System.out.println(count);
        }
    
    
        private static boolean judge2(BigInteger i) {
        
            if (i.compareTo(BigInteger.valueOf(3)) == 0 || i.compareTo(BigInteger.valueOf(5)) == 0 || i.compareTo(BigInteger.valueOf(7)) == 0)
                return true;
            while (i.mod(BigInteger.valueOf(3)).compareTo(BigInteger.valueOf(0)) == 0)
                i = i.divide(BigInteger.valueOf(3));
            while (i.mod(BigInteger.valueOf(5)).compareTo(BigInteger.valueOf(0)) == 0)
                i = i.divide(BigInteger.valueOf(5));
            while (i.mod(BigInteger.valueOf(7)).compareTo(BigInteger.valueOf(0)) == 0)
                i = i.divide(BigInteger.valueOf(7));
            return i.compareTo(BigInteger.valueOf(1)) == 0;
        }
    
        private static boolean judge(BigInteger num) {
        
            boolean flag = Integer.parseInt(num.mod(BigInteger.valueOf(3)).toString()) == 0 || Integer.parseInt(num.mod(BigInteger.valueOf(5)).toString()) == 0 || Integer.parseInt(num.mod(BigInteger.valueOf(7)).toString()) == 0;
            BigInteger temp = new BigInteger(String.valueOf(2));
            while (true) {
        
                if (temp.compareTo(num) < 0) {
        
                    if (!judge2(temp))
                        if (Integer.parseInt(num.mod(temp).toString()) == 0) {
        
                            flag = false;
                            break;
                        }
                    temp = temp.add(BigInteger.valueOf(1));
                } else
                    break;
            }
            return flag;
        }
    }

> 就在我以为大功告成的时候，将数字改为59084709587505（用long存储 ），发现hashset爆栈了或者是一直跑不出来——超时了！这题这么有难吗？怎么办呢？接着往下看！

## 正确思路（一） ##

这里说一下我后来想到的办法，可能还能做优化，但是目前已经是能用的了，如有更好的方法，请在评论区留言指点，不胜感激！

***其实这类题和快速幂等数论思想一样，从已知条件入手，不考虑无关内容，从而优化循环，降低复杂度***

> **解题思路：**  
> 由于因子只含有3,5,7，所以满足该条件的数一定是由 ： 3的某次方 \* 5的某次方 \* 7的某次方 构成，而这样组成的数相对于全部的数，它们只占少部分，则可以直接暴力求解！  
> 定义三个变量，三个变量都从0开始，因为一个数的0次方法等于1，相乘不会影响结果，但需要注意的是，要排除掉1这个数字，并且给定的那个数是需要取到的，所以我们列出公式：  
> for (int x = 0; Math.pow(3, x) <= num; x++)  
> for (int y = 0; Math.pow(5, y) <= num; y++)  
> for (int z = 0; Math.pow(7, z) <= num; z++)  
> 这样就能遍历出全部的“幸运数字”，然后加以判断，只要“幸运数字”是<=number的，就追加个数。  
> 代码如下（Java）：

public class Main {
        
    
        public static void main(String[] args) {
        
            long num = 59084709587505L;
            int count = 0;
            for (int x = 0; Math.pow(3, x) <= num; x++)
                for (int y = 0; Math.pow(5, y) <= num; y++)
                    for (int z = 0; Math.pow(7, z) <= num; z++)
                        if (Math.pow(3, x) * Math.pow(5, y) * Math.pow(7, z) <= num)
                            count++;
    
            System.out.println(count - 1);
        }
    }

--------------------

## 总结 ##

`当我们初次接触到这类问题时，总是以最直观的方法进行求解，却没有想到耗时问题；应该仔细分析已知条件，从已知的条件入手能够排除掉很多无关的数字，从而大大降低时间空间开销！`

文章粗浅，希望对大家有帮助！