数论——因子组合

简介: 数论——因子组合

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

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

题目

到 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);
    }
}

总结

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

文章粗浅,希望对大家有帮助!

相关文章
|
6天前
【代数学作业5】理想的分解:高斯整数环中理想的结构,并根据其范数和素数的性质进行分解
【代数学作业5】理想的分解:高斯整数环中理想的结构,并根据其范数和素数的性质进行分解
37 0
|
6天前
|
机器学习/深度学习 人工智能 算法
【代数学作业1-python实现GNFS一般数域筛】构造特定的整系数不可约多项式:涉及素数、模运算和优化问题
【代数学作业1-python实现GNFS一般数域筛】构造特定的整系数不可约多项式:涉及素数、模运算和优化问题
59 0
|
6天前
|
算法 BI 测试技术
【唯一分解定理 数学】1808好因子的最大数目
【唯一分解定理 数学】1808好因子的最大数目
【唯一分解定理 数学】1808好因子的最大数目
|
9月前
|
存储 Java
数论——因子组合
数论——因子组合
|
5月前
构造命题公式的真值表
构造命题公式的真值表
75 0
|
机器学习/深度学习
【数论】计算s里有几个n,去除s里的n
【数论】计算s里有几个n,去除s里的n
65 0
【矩阵分析】矩阵幂级数 发散 条件 || 幂级数 与 解析函数 的关系 || 幂级数 收敛半径r 的求法
【矩阵分析】矩阵幂级数 发散 条件 || 幂级数 与 解析函数 的关系 || 幂级数 收敛半径r 的求法
【矩阵分析】矩阵幂级数 发散 条件 || 幂级数 与 解析函数 的关系 || 幂级数 收敛半径r 的求法
|
存储 算法
算法 |【实验5.3】:一元三次方程的根-连续区间的二分搜索求近似解
算法 |【实验5.3】:一元三次方程的根-连续区间的二分搜索求近似解
126 0
算法 |【实验5.3】:一元三次方程的根-连续区间的二分搜索求近似解
再学一道算法题:矩阵A乘以B
再学一道算法题:矩阵A乘以B
再学一道算法题:矩阵A乘以B
排列组合相关公式讲解(Anm,Cnm等)
排列组合相关公式讲解(Anm,Cnm等)
2108 0
排列组合相关公式讲解(Anm,Cnm等)