对一个无比巨大的数求7的模

Question

题目：
  一个巨大无比的数字（现有的内存无法容纳，只能存储在磁盘文件中），求该数对7的模！半夜看到一个提问这个的帖子，心血来潮捣鼓了下，花了我3小时，觉得蛮有意思就变成自己开帖子了，欢迎讨论！首先，如果这个数能够被BigInteger装得下，那么就直接取模就OK了
如果这个数实在是大到没有办法用内存来装它的话，那么对于7的模，我还有办法：首先是理论依据：
1、取模的性质：(a+b)%c=(a%c+b%c)%c;
    这个性质是我的解法的基础，对于任意一个数，比如31246而言：
    31246%7=(30000%7+1000%7+200%7+40%7+6%7)%7
    因此，只要能够将该数按位(十进制)分拆开来计算7的模，并汇总之后模7即可！
2、我的解法关键就是如何计算每一个位对7的模，以下是我写的一个测试程序：    BigInteger mod=new BigInteger("7");
    for(int i=0;i<100;i++){
      for(int j=0;j<10;j++){
        BigInteger bi=new BigInteger("10");
        BigInteger b=new BigInteger(String.valueOf(j));
        bi=bi.pow(i).multiply(b).mod(mod);
        System.out.print(" "+bi);
      }
      System.out.println();
    }其输出结果如下：
 0 1 2 3 4 5 6 0 1 2
 0 3 6 2 5 1 4 0 3 6
 0 2 4 6 1 3 5 0 2 4
 0 6 5 4 3 2 1 0 6 5
 0 4 1 5 2 6 3 0 4 1
 0 5 3 1 6 4 2 0 5 3
 0 1 2 3 4 5 6 0 1 2
 0 3 6 2 5 1 4 0 3 6
 0 2 4 6 1 3 5 0 2 4
 0 6 5 4 3 2 1 0 6 5
 0 4 1 5 2 6 3 0 4 1
 0 5 3 1 6 4 2 0 5 3
 0 1 2 3 4 5 6 0 1 2
 0 3 6 2 5 1 4 0 3 6
 0 2 4 6 1 3 5 0 2 4
 0 6 5 4 3 2 1 0 6 5
  .................
可以发现，0-9的十个数字中除了0和7之外，它们从个十百千万不断提升位数时，对7的模总是按照一定的规律：132645132645...不断地循环，只是个位数上的起始循环位置的不同，那么这就为计算nEx对7的模提供了一定的可能
（虽然我不能证明当x非常大的时候这个规律仍然有效，但是这一发现已经让我兴奋得无法承认它不可靠，就算错也让它一错到底吧！）
下面是一个演示程序，如果真要让它处理巨大的数字，肯定会需要用文件流来操作，我只想演示这个过程可行，就不费那神了：    int[][] base=new int[][]{{1,3,2,6,4,5},{2,6,4,5,1,3},{3,2,6,4,5,1},{4,5,1,3,2,6},{5,1,3,2,6,4},{6,4,5,1,3,2}};
    byte[] buf="17777777777777777777715".getBytes();
    int mod=0,ccnt=0;
    for(int i=buf.length-1;i>=0;i--,ccnt++){// 从个位数往高位依次处理
      int d=buf[i]&0x0F;// ASCII to number
      d%=7;// 8,9的情况与1，2相同,so...
      if(d==0) continue;
      int index=ccnt%6;
      mod+=base[d-1][index];
      mod%=7;
    }
    System.out.println(mod);我没过多地测试这个程序，可能还有BUG也说不定，至少这个程序应该能够证明，能够有一种手段对可以使用“流”的方式来计算7的模，我不想继续花时间在这个小程序上，因为我现在更想知道和思考如果不是7的话，是不是也有类似的解决方案，有没有通用的解决方案呢？

Answer 1

沙发！！！
昨天我也看到那个帖子
当然也想到用BigInteger来对7取模
但感觉 要是直接转成BigInteger来进行运算的话
这似乎不是面试官的意图
这样的话 就跟普通的运算没什么两样
应该是有什么比较好的算法
继续关注 高手们的解答
顶！！！！

Answer 2

他的意图？只要能解决他的问题。。用什么方法解决不是一样么。。其实这个就是用截取字符的方法就可以轻易解决了截取一个int或者long类型可以装下的数字，然后对N进行取余，如果有余数则把余数加到下一次截取的数字前面再次进行截取，，知道截取完。。然后就可以判断余数了。。如果余数是0当然可以被整除。。如果余数为 y 那么 只要y加上N-y的数就可以被n整除。。即可。
向你说的。。我先用流读进来一部分来计算

Answer 3

我想到一个方法，你可以参考一上。
既然是7的模，你可以一部分一部分的读，有一个道理就是，7可以被7×10的整数倍除，对于1 2 3 4 5 ....
这种数字，你可以先计算1 2 3 % 7的值，结果为6,那么再将6和后面的一部分继续处理，就成了6 4 5 ...这样的了。
这种处理一种继续，最后就成了一个int以内的计算了。
实际上一个数以写成 X(模） + 7 * 10 + 7 * 100 + 7 *1000，这种的写法
那么，我们就可以倒算，先减到7*10X 这种，最后就自然得到最后的模了。还有一个简单的算法，对于大数，不管是什么，先对每个数-7,比如97，可以当成(9-7)(7-0)这样，即20来算，结果算出来的模和 97算出来的模是一样的。这两种算法，相互结合，结果一定很快，可以达到最快速的计算。

Answer 4

除以一个数，不用一次性全读入，几位几位的读入，不够再借位
import java.math.BigInteger;
import java.util.Random;public class Test {
    public static void main(String[] args) {
        final int number = 7;
        Random rand = new Random(System.nanoTime());
        StringBuilder sb = new StringBuilder();
        
        // 测试
        System.out.println("字符串一次性求模");
        for (int i = 0; i < 50; ++i) {
            sb.append(rand.nextInt(10));
            String str = sb.toString();
            System.out.println(str);
            
            System.out.println("My: " + calculateMod(str, number, 5));
            System.out.println("Bi: " + new BigInteger(str).mod(new BigInteger(number + "")));
            
            System.out.println();
        }
        
        System.out.println("\n字符串分解成多个子串求模");
        sb.delete(0, sb.length());
        int mod = 0;
        for (int i = 0; i < 50; ++i) {
            int value = rand.nextInt(10);
            sb.append(value);
            String str = sb.toString();
            System.out.println(str);
            
            // 把一个大串分成多个部分来进行求模
            mod = calculateMod(mod + "" + value, number, 5);
            System.out.println("My: " + mod);
            System.out.println("Bi: " + new BigInteger(str).mod(new BigInteger(number + "")));
            
            System.out.println();
        }
    }    // 求表示整数的字符串str对整数number的模，dx表示读取子串的长度
    public static int calculateMod(String str, final int number, final int dx) {
        int mod = 0;
        int end = 0;
        for (int i = 0; i < str.length(); i += dx) {
            end = i + dx;
            end = end > str.length() ? str.length() : end;
            String temp = str.substring(i, end);
            
            mod = mod * (int)(Math.pow(10, temp.length())) + Integer.parseInt(temp);
            mod %= number;
        }        return mod;
    }
}

Answer 5

10楼的兄弟，即使BigInteger能够装得足够大    Date start=new Date();
    BigInteger bi=new BigInteger("10");
    bi=bi.pow(100000);
    System.out.println(bi.toString().length());
    System.out.println(new Date().getTime()-start.getTime());差不多要3秒，所以你的思路在输入数据规模很大的时候时间开销与输入长度不成正比！

Answer 6

根据(a+b)%c=(a%c+b%c)%c;比如 232%7 = （200%7 + 30%7 + 2%7）%7 = （4+2+2）% 7 = 1
并且
1对7的余数为1
10对7的余数为3
100对7的余数为2
1000对7的余数为6
10000对7的余数为4
100000对7的余数为5
1000000对7的余数为1
接下来为132645的循环。
继续求232应该为；
(（2 * 100%7）%7  + (3 * 10%7)%7 + (2 * 1%7)%7 ) %7 =( (2*2)%7 + (3*3)%7 + (2*1)%7 )%7 = 8%7=1
对大数可以依次类推

Answer 7

BigInteger是用来验证自己算法的正确性，不是拿来求模的
而且楼主说得很清楚，这个数可以大到内存装不下，所以BigInteger不能解决这个问题

Answer 8

因为7和3（10-7）互质，所以数字数位提升的时候才会发生每数字循环的现象。如果不是互质，则后面会变成0
如 1%8=1 10%8=2 100%8=4 1000%8=0，之后就是全0了而楼主判断大数余数的算法的不足在与是从低位到高位计算的，所以需要全部读入内存，然后处理。其实完全可以从高位往低位逐位计算。
只要一个循环，逐字符读入文件，就可以完成计算了。
原理；
若数字A%x=a
则进位后10A % x = (10 * (A % x)) % x
程序稍后再贴

Answer 9

public class Test {    private final static int[] MODS = { 1, 3, 2, 6, 4, 5 };    public static void main(String[] args) {
        System.out.println(mod7("17777777777777777777715"));
    }    public static int mod7(String num) {
        int sign = 1;
        char[] digits = null;
        if(num.charAt(0) == '-') {
            sign = -1;
            digits = num.substring(1).toCharArray();
        } else {
            digits = num.toCharArray();
        }
        int mod = 0;
        int k = digits.length;
        for(int i = k - 1; i > -1; i--) {
            mod += MODS[(k - i - 1) % MODS.length] * (digits[i] - '0');
            mod %= 7;
        }
        return mod * sign;
    }
}

Answer 10

续16楼，贴代码
真的很简单哦public class ModOfNumberInFile {
public static void main(String[] args) throws IOException {
Reader f = new FileReader("number.txt"); //大数在此文件中，字符形式记录
int d;
int result = 0;
while((d=f.read())!=-1){
result = (result*10+((char)d-'0'))%7;
}
System.out.println("文件中数Mod7的余数是：" + result);
}
}
楼上火龙果的代码也不长，不过还没看明白。再看看。

Answer 11

逐位计算太慢了，可以9位一起计算，9位是亿，int最大是20亿左右

Answer 12

只要做一次mod运算即可。public class Test {
static String num = "14141412345787709787897419874985791709878925723758923752897592837279701751751881758573153"+
"3091888883098127489175891275871892759175091729571927509170917";
static int[] mods = new int[]{1,3,2,6,4,5};

public static void main(String[] args) {
long time1 = System.nanoTime();
int result = 0;
for(int i = 0;i < num.length();i++){
result += Integer.parseInt(num.charAt(num.length() - i - 1)+"") * mods[i % mods.length];
}
result %= 7;
long time2 = System.nanoTime();
System.out.println("数字长度:" + num.length());
System.out.println("结果:" + result);
System.out.println("时间:" + (time2-time1)* 1.0/Math.pow(10, 9)+"秒");
}}省略了读文件的过程。
结果：
数字长度:150
结果:6
时间:6.27917E-4秒

Answer 13

这道题的关键在于规律，所以也算变相考数论了。
基于一般规律 (a+b)%c=(a%c+b%c)%c; ①考虑的，19L，26L给出了程序，不过26L的有点考虑不足，数据过大，result在for里就溢出了。
16L给出的规律挺好的，(10*A) % x = (10 * (A % x)) % x ② ，20L给出了代码
这里就替20L解释一下20L的代码吧
假设A%x=result，那么根据一般规律①展开，(10*A+B)%x = ((10*A)%x + B%x)%x
根据②规律，(10*A) % x = (10 * (A % x)) % x代入右边
(10*A+B)%x = (10*(A%x) + B%x)%x = (10*result + B%x)%x
根据一般规律①展开，(10*result + B%x)%x = ((10*result)%x + (B%x)%x)%x
而我们知道，一个数对某个数取余后在对该某个数取余还是等于头一次取余的结果，
即A%x == (A%x)%x == ((A%x)%x)%x ... ，不管后面多少次重复取余，结果都是头一次
所以((10*result)%x + (B%x)%x)%x = ((10*result)%x + B%x)%x
根据一般规律①等号两边交换位置，((10*result)%x + B%x)%x = (10*result + B)%x
所以(10*A+B)%x = (10*result + B)%x，把(10*A+B)%x看成下一个result，于是可得20L的代码
result = (result*10+((char)d-'0'))%7;

Answer 14

上面有点小失误（不过也能成立），改正出在以下红色部分
假设A%x=result，那么根据一般规律①展开，(10*A+B)%x = ((10*A)%x + B%x)%x
根据②规律，(10*A) % x = (10 * (A % x)) % x代入右边
(10*A+B)%x = ((10*(A%x))%x + B%x)%x = ((10*result)%x + B%x)%x根据一般规律①等号两边交换位置，((10*result)%x + B%x)%x = (10*result + B)%x
所以(10*A+B)%x = (10*result + B)%x，把(10*A+B)%x看成下一个result，于是可得20L的代码
result = (result*10+((char)d-'0'))%7;

Answer 15

10L和16L(20L)的规律是一样的
即 (A*B)%x = (A*(B%x))%x = ((A%x)*(B%x))%x
所以20L的 result = (result*10+((char)d-'0'))%7; 改为
result = (result*(10%7)+((char)d-'0'))%7; 即result = (result*3+((char)d-'0'))%7;结果是一样的
result = (result*10+((char)d-'0'))%7; 用到了(A*B)%x = (A*(B%x))%x
result = (result*3+((char)d-'0'))%7;用到了(A*B)%x = ((A%x)*(B%x))%x而10L的 mod相当于20L的result，(int)(Math.pow(10, temp.length())) 相当于10，Integer.parseInt(temp)相当于(char)d-'0'10L代码测试代码部分过多，核心部分没突出，所以一开始没看，忽略了，现在细看才发现10L和20L的是在同一规律的基础上实现的，只是20L是一位一位算，10L是多位多位算的，只要保证多位的时候不超出int范围就可以。