今天去华为赛门铁克面试被提到的一个问题（JAVA）

Question

String str = "5673454322...............323223";
str是一个无穷大的数字,一个long都无法放入，假设一个n值是7。
面试官提问：如何使得这个数字可以被n整除？？？

Answer 1

public static void main(String[] args) {
BigInteger big = new BigInteger("54354358093245892583457839730957349857394857367935384895");
System.out.println("余数是"+big.divideAndRemainder(BigInteger.valueOf(7))[1].toString());
}

Answer 2

public static void main(String[] args) {
String str = "54354358093245892583457839730957349857394857367935384895";
int n= 7;
String yushu = "";
if(str.length()<5){
yushu=String.valueOf(Integer.parseInt(str)%n);
}else{
for (int i = 0; i < str.length()/5; i=i+5) {

String temp = yushu+str.substring(i, i+5);
int cloum = Integer.parseInt(temp);
int yu = cloum%n;

if(yu!=0){
yushu=String.valueOf(yu);
}else{
yushu="";
}
}
}
if(yushu.length()<=0||"0".equals(yushu)){
System.out.println("可以被整除");
}else{
System.out.println("不可以被整除");
}

}
这是我自己实现的一个

Answer 3

BigInteger会有多大，String可以直接转成他么，我觉得面试人的问题是说似乎任何类型都不能放下这个数？

Answer 4

题目翻译一下：有不定大小的数字x，求与x之间差值最小的7的公约数，给出差值大小
例：
   x = 15
   设y,且y%7=0
   答案就是 x+(y-x)
小于long长度的数字直接用long计算
大于long长度的算法没想好，哈哈
   

Answer 5

如果是按照你说的做的话这样就可以了：public static void main(String[] args) {
String str = "56546456054958947658670943860483693423243433437430698390683915";
int n= 7;
String yushu = "";
if(str.length()<5){
yushu=String.valueOf(Integer.parseInt(str)%n);
}else{
for (int i = 0; i < str.length(); i=i+5) {
String temp = null;
if(i!=str.length()/5*5) 
temp = yushu+str.substring(i, i+5);
else
temp = yushu+str.substring(i, str.length());
int cloum = Integer.parseInt(temp);
int yu = cloum%n;

if(yu!=0){
yushu=String.valueOf(yu);
}else{
yushu="";
}
   }
}
if(yushu.length()<=0||"0".equals(yushu)){
System.out.println("可以被整除");
}else{
System.out.println("当str加上"+(n-Integer.parseInt(yushu))+"既可以被"+n+"整除");
}

}

Answer 6

public static void main(String[] args) {
final int leg=18;
StringBuilder str=new StringBuilder("49793821479387619794872314840");
int n=7;
long count=0;

while(true){
long num;
if(str.length()<=leg){
num=Long.parseLong(str.substring(0, str.length()));
count+=num%n;
break;
}else{
num=Long.parseLong(str.substring(0, leg));
count+=num%n;
str.delete(0, leg);
}
}
System.out.println(count%n==0?"可以":"不可以");
}

Answer 7

多了，那里可以不截取 
if(str.length()<=leg){
     num=Long.parseLong(str.toString()));
     count+=num%n;
     break;
}

Answer 8

BigInteger理论是可以无穷大的
但觉得面试官应该不是这个意图吧
若是这样 用BigIntger来表示的话 跟普通的除法 没什么两样

Answer 9

就我的观点来看，这应该是一道大数乘法的变形题，基本思路如下：
将大数从最高位开始截取k位（将这k位转化为数字后应该在long范围之内），然后进行除法运算，再截取k-1位，将其与所得余数连接。依次进行，如果最后一次运算余数为零说明能被n整除。
上面的思路假设了除数在long范围内

Answer 10

这个是有规律的，之后根据同余定理计算其中：
i — 从右边数起的第几位数字
xi — 从右边数起第 i 位上的数字值
p — 总共的数字位数
n — 模几
k — 计算结果
 

Answer 11

楼上的兄弟们都小学没有毕业啊题目也没看懂。。
判断str 是否被n整除，没让判断mod后的值，明显用小学的割尾法去做。

Answer 12

判断整除不就是 mod 等于 0 么？

Answer 13

搜一下 小学奥赛"论文"，割尾算法。。哎整天就知道MOD....

Answer 14

从高位开始逐个读入字符串，然后mod 7，记录余数，读到下一位时将余数*10+当前的值，继续mod 7，记录余数......String str = "5673454322...............323223";
一下为余数部分
5 0 0 3 6 2 3 6 0 2 1...... 

Answer 15

所谓的割尾法不知道是出自何人之手
纯粹的误人子弟
用同余公式写出来的代码如 litaoye 兄给的那个
姑且叫“砍头”法吧 
完全比所谓的割尾法简单的多

Answer 16

String a = "1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890";

char[] arr = a.toCharArray();
int[] int_array = new int[arr.length];
for(int j=0;j<arr.length;j++){
int_array[j]=arr[j]-48;
}

for(int i = 0 ; i < int_array.length-3; i++){
int_array[i+3]=(int_array[i+3]-int_array[i]);
int_array[i] = 0;
}
int result = (int_array[arr.length-1]+int_array[arr.length-2]*10+int_array[arr.length-3]*10*10)%7;
System.out.println(result<0?result+7:result);
// System.out.println(Integer.parseInt(a)%7);
考虑到1001能够被7整除，于是把前面的数字都干掉，只留下最后3位。
然后求余应该有更好的方法的。。就是想不出来。。

Answer 17

public static void check(String str){
String tmp = str; if(tmp.length() < String.valueOf(Long.MAX_VALUE).length()){ long last = Long.parseLong(tmp);
long re = last % 7;
if(re == 0){
System.out.println("over:"+re);
}else{
System.err.println("err:"+re);
}
return;
}

int l = Integer.parseInt(tmp.substring(tmp.length() - 1, tmp.length()));
int h = Integer.parseInt(tmp.substring(tmp.length() - 4, tmp.length() - 1));
int e = h - 2*l;

tmp = tmp.substring(0, tmp.length() - 4);
tmp += String.valueOf(e);
check(tmp);
}刚才找了一下割尾法的说明，写了这个。

Answer 18

以n-1为长度从低到高为字符串分割，然后对每部分进行mod n运算，最后累加这些和再mod n
例
12345687878798872 % 7
12345 % 7 = 4
687878 % 7 = 2
798872 % 7 = 4（4+2+4） % 7 = 3

Answer 19

public class Test{
public static void main(String[] args) {
//10求余7等于3 100->2 1000->6 10000->4 100000->5 1000000->1  后面为循环10000000->3 。
//20%7=2*(10%7)  300%7=3*(100%7)....... (如果右边的结果大于7请不要纠结这个问题)
String s = "143343434434";
int st = Integer.parseInt(s.substring(s.length()-1));//先把个位数抽出来，因为它不再规律之内 String s1= s.substring(0, s.length()-1);//抽出个位剩余的数


int last = s1.length()%6;//6为循环基数。比如 s1为15位， 那么最大的3位就要另外处理
String ss1 = s1.substring(0, last); String ss2 = s1.substring(last, s1.length());//抽出另外需要处理的

if (!ss1.equals("")) {
int k = 1;
char ch[]=ss1.toCharArray();
for (int i = ch.length-1; i >=0; i--) {
if (k==1) {
st+=Integer.parseInt( Character.toString(ch[i]))*3;
k+=1;
}
else if (k==2) {
st+=Integer.parseInt( Character.toString(ch[i]))*2;
k+=1;
}
else if (k==3) {
st+=Integer.parseInt( Character.toString(ch[i]))*6;
k+=1;
}
else if (k==4) {
st+=Integer.parseInt( Character.toString(ch[i]))*4;
k+=1;
}
else if (k==5) {
st+=Integer.parseInt( Character.toString(ch[i]))*5;
k+=1;
}
else if (k==6) {
st+=Integer.parseInt( Character.toString(ch[i]))*1;//这个其实不会参与进来
k+=1;
}
}
}

//下面是完整的循环的
if (!ss2.equals("")) {
int k = 1;
char ch[]=ss2.toCharArray();
for (int i = ch.length-1; i >=0; i--) {
if (k%6==1) {
st+=Integer.parseInt( Character.toString(ch[i]))*3;
k++;
}
else if (k%6==2) {
st+=Integer.parseInt( Character.toString(ch[i]))*2;
k++;
}
else if (k%6==3) {
st+=Integer.parseInt( Character.toString(ch[i]))*6;
k++;
}
else if (k%6==4) {
st+=Integer.parseInt( Character.toString(ch[i]))*4;
k++;
}
else if (k%6==5) {
st+=Integer.parseInt( Character.toString(ch[i]))*5;
k++;
}
else if (k%6==0) {
st+=Integer.parseInt( Character.toString(ch[i]))*1;
k++;
}
}
}

System.out.println(Long.parseLong(s)%7);//只用long验证下了
System.out.println(st%7);
}
}

Answer 20

Integer的最大值是10位，那么可以9位9位的截取出来，求出余数，
然后求出 Math.pow(10,9)的余数，进行相乘
最后剩余位数不足9位，就再求一次Math.pow(10,n)的余数,然后和之前的余数相乘，加上尾数。

Answer 21

对一个很大很大的数字 感觉可以用脚本引擎 调用JavaScript的excu（）方法去计算 这样理论上是不是可以计算无穷大的数啊

Answer 22

精彩的回答 出口恶气 litaoye 的算法确实不错
可以实现任意大的数对7求mod
我试过了 
呵呵

Answer 23

哎 技不如人啊 想了好久public class test { /**
 * 求一个由数字组成的任意长度的字符串能否被N整出
 * @param args
 */
public static void main(String[] args) {
// TODO Auto-generated method stub
 String str = "54354358093245892583457839730957349857394857367935384895";
        int n= 7;
        int tmp = 0;
        for(int i =0;i<str.length();i++){
         tmp = (Integer.parseInt(str.charAt(i)+"")+tmp) % n;
         System.out.println(tmp);
        }
        if(tmp == 0){
            System.out.println("可以被整除");
        }else{
            System.out.println("当str加上"+(n-tmp)+"既可以被"+n+"整除");
        }
}
}

Answer 24

这方法不错，容易理解。public static void checkHead(String str, int n){

String tmp = str;
int e = 0;

for(int i = 0 ; i < tmp.length() ; i ++){
int h = Integer.parseInt(tmp.substring(i, i + 1));
e = (e*10 + h) % n;
}

if(e == 0){
System.out.println("over h:" + e);
}else{
System.err.println("err h:" + e);
}

}

Answer 25

我这也有个方法，只写了个算出余数的方法，怎样加进去就不写了。public class TT {

public static void main(String[] args) {
String str = "328493539952757478850238985656747746634635864599499999900";
int n = 7;
String rimainder = result(str,n);
System.out.println(rimainder);

}

public static String result(String str, int n) {
String[] sa = stringArray(str);
if(sa.length>1) {
int rimainder = Integer.valueOf(sa[0])%n;
String newstr = Integer.toString(rimainder);
sa[1] = newstr+sa[1];
return result(sa[1],n);
}
else return Integer.toString((Integer.valueOf(sa[0])%n));
}

private static String[] stringArray(String str) {
if(str.length()<10) {
String[] sa = {str};
return sa;
}
String[] sa = {str.substring(0, 9),str.substring(9, str.length())};
return sa;
}
}

Answer 26

我想到的也是读入一定长度的str求余，然后这样不断的读取就可以了

Answer 27

大家的回答其实都忽略了一种情况
如果被除数不是7，而是 Long.MAX_VALUE+1之类的大数的话
以上的代码还有几个能用的？

Answer 28

String str = "5673454322...............323223";
既然str是一个无穷大的数字,一个long都无法放入 ,你们做这样的
"String.valueOf(Integer.parseInt(str)%n);”
或者" long num=Long.parseLong(str.substring(0, leg));"
有什么意义呢？。。

Answer 29

无语，哥们看清楚代码，人家是先判断str的长度的

Answer 30

我也提供一种实现方法，基本思想就是移位。
经测试通过。public class BigIntegerzhengchu {
public static void main(String[] args) {
boolean result = isDividend("777777777777777777777777777777", "7777");
if (result)
System.out.println("整除");
else
System.out.println("不能整除");
} //利用从左到右移位实现判断被除数被除数整除
static boolean isDividend(String dividend, String divisor) {
int divisorI = Integer.parseInt(divisor);
String firstN = dividend.substring(0, divisor.length());
int firstNI = Integer.parseInt(firstN);
int result = firstNI - divisorI;
if (result < 0) {
result = firstNI;
} else if (result > 0 || result == 0) {
result = firstNI - divisorI;
}
for (int i = divisor.length(); i < dividend.length(); i++) {
result = result*10 + Integer.parseInt(dividend.substring(i, i + 1));
result = result % divisorI;
}
if (result == 0)
return true;
else
return false;
}
}

Answer 31

这不是在考java，是在考奥数呢，赛门铁克不做软件，做奥数题库了，.......

Answer 32

这不是在考java，是在考奥数呢，赛门铁克不做软件，做奥数题库了，.......

Answer 33

还真搜了一下，不管是google还是baidu，都没搜到－－奥赛"论文"，割尾算法，还真不知道这个方法有什么好处，...........

Answer 34

这是个数学问题，原题目可以等价为如下形式：
若一个整数的个位数字截去，再从余下的数中，减去个位数的2倍，如果差是7的倍数，则原数能被7整除。
证明过程是这样的：
对一个n位数a来说，把它表示为 a=10x+y，其中y是a的个位数，x是a去掉个位数y后的n-1位数。
根据同余定理a≡10x+y (mod 7)≡7x+7y+3x-6y (mod 7)≡7(x+y)+3(x-2y) (mod 7)≡x-2y (mod 7)
如判断6146是否能被7整除的过程：614-6×2=602，60-2×2=56，所以6146能被7整除。
类似的能否被11、13整除，都能用这种方法计算，但是如果无法转换成x+ny（n为整数）的形式就不利于计算机求解了。

Answer 35

大家看看我的代码吧public static void main(String[] args) {
String str = "14777777777777777777777777771";
int temp = 0;
int n = 7;
for(int i=0;i<str.length();i++){
int y =Integer.parseInt(""+str.charAt(i));
temp =((temp*10)+y)%n;
}
System.out.println(temp==0 ? true:false);
}

Answer 36

http://zhoushijingguo.blog.163.com/blog/static/15359663620109184520680/可以参见这个博客

Answer 37

上面有哥们说是考奥数，我看不见得，奥数可比这个难多了！
我们小学一年级或是二年级都学过除法运算的规则，程序实现时我们只要把除法运算的规则搬过来就可以了。
假设int型可以放N位数，我们每次从左至右取N-2个（减2是为了，加余数）除以7产生余数m，然后再去后面的N-2加上m*10^N-2再除7产生余数m，然后以上述方法循环
到最后一次如果位数N0小于N-2，则全部取完，加上m*10^N0,然后除7产生余数m，判断此时余数是否为零。
老板问的是怎么让它可以整除7，只要对后面的N0位减去m  或加上7-m就好了。

Answer 38

package com.cn;public class Div7 {
public static void main(String[] args) {
String str = "7777777777777777777777777777777777777776";
char[] ch = new char[str.length()];
str.getChars(0,str.length(),ch,0);
String[] value = new String[str.length()];
int[]  n = new int[str.length()];
for (int i = 0; i < str.length(); i ++) {
value[i] = "" + ch[i];
n[i] = Integer.parseInt(value[i]);
System.out.print(n[i]);

}
System.out.println("");
bet(n);


}
/**
 * 若一个整数的个位数字截去，再从余下的数中，减去个位数的2倍，如果差是7的倍数
 * ，则原数能被7整除。如果差太大或心算不易看出是否7的倍数，就需要继续上述
 * 「截尾、倍大、相减、验差」的过程，直到能清楚判断为止。例如，判断133是否7的
 * 倍数的过程如下：13－3×2＝7，所以133是7的倍数；又例如判断6139是否7的倍数的
 * 过程如下：613－9×2＝595 ， 59－5×2＝49，所以6139是7的倍数，余类推.
 * @param n
 */
private static void bet (int[] n) {
int m = n.length;
int b = 0;
int i =0;
for (i = 0;i < n.length - 3; i++) {
b = n[m -  4]*100 + n[m - 3]*10 + n[m -2];
System.out.println(b);
b = b - 2*n[m - 1];
n[m - 4] = b/100;
n[m - 3] = b%100/10;
n[m - 2] = b%10;
n[m - 1] = 0;
m--;
for (int j = 0;j < n.length; j ++) {
System.out.print(n[j]);
}
System.out.println("");
}

System.out.println(m + "m:b" + b);
if (3 == m) {
b = n[0]*100 + n[1]*10 + n[2];
if(b%7 == 0) {
System.out.println("yes!");
}
else {
System.out.println("no!");
}
}
else if (2 == m) {
b = n[0]*10 + n[1];
if(b%7 == 0) {
System.out.println("yes!");
}
else {
System.out.println("no!");
}
}
else if (1 ==m ) {
if(b%7 == 0) {
System.out.println("yes!");
}
else {
System.out.println("no!");
}
}
}
}时间复杂度：O(大数的位数）

Answer 39

   /**
    * 
    * @param val such as "5673454322...............323223"
    * @param divide such as 7
    * @return if divisibility return 0
    */
   public static int division(String val, int divide) {
      int len = 5;
      int number = 0;
      int mod = -1;
      String s = "";      while(val.length() > 0) {
         if(val.length() > len) {
            s = val.substring(0, len);
            val = val.substring(len);
         }
         else {
            s = val.substring(0, val.length());
            val = "";
         }         number = Integer.parseInt((mod == -1 ? 0 : mod) + s);
         mod = number % divide;
      }      return mod;
   }

Answer 40

还用这么费劲吗？从最前面开始对7取余，如果能整除则去掉该位数，不能整除余数+后面的数再对7取余（重复这个过程）。例如3665886这个数，首先3对7取余（简称mod），剩3
然后36 mod 7 = 1, 整个数变成165886
165886重复这个过程2588648866865656 mod 7 ==0 ,所以能被整除。 如果最后不等于0则表示不能被整除。不管字符串长度是多少，每次至多取出前两位进行mod 7,因此也不用什么biginteger,用个short都足够了。算法的时间 N次mod 7 运算， N=字符串长度。刚开始被误导了，寻思了半天。大家都想复杂了。 再试一个：41272004127200627200672004200000 ==0 特殊情况就不再举例，重点突出解决问题的思路。

Answer 41

求余规律
(a*b)%c = (a*(b%c))%c = ((a%c)*(b%c))%c
(a+b)%c = (a%c + b%c)%c
一个数，可以写成 a*10^n + b (其中b是n位数)
比如2位数 52 = 5*10 + 2; (n=1) 
3位数 572 = 5*100 + 72 (n=2) = 57*10 + 2 (n=1)
4位数 5872 = 5*1000 + 873 (n=3) = 58*100 + 72 (n=2) = 587*10 + 2 (n=1)所以，利用上面的定理，可以得到
(a*10^n + b)%c 
= ((a*10^n)%c + b%c)%c
= (((a%c)*10^n)%c + b%c)%c如果一个数，从左到右来取，那么把 a%c 看作第一次取数求余的结果，那么完整的结果就是下一次求余结果
于是可得
result = ((result%c)*10^n + b%c)%c
即
public int Mod(String data, int num) { //data是任意长度的字符串
    int result = 0;
    for (char c : data.toCharArray()) { //这里是按一位一位取，也可以用substring按多位取，转为int或long范围内的数据计算
        result = ((result%num)*10 + ((int)(c-'0'))%num) % num;
    }
    return result;
} 
如果一个数，从右往左取，那么把 b%c 看作第一次取数求余的结果，，那么完整的结果就是下一次求余结果
于是可得
result = ((a%c)*10^n + result)%c
即
public int Mod(String data, int num) { //data是任意长度的字符串
    int result = 0;
    char[] ca = data.toCharArray();
    for (int i=ca.length-1; i>=0; i--) { 
        result = ((((int)(c[i]-'0'))%num)*10 + result%num) % num;
    }
    return result;
}  

Answer 42

这个问题很简单的嘛，思想跟上面的童鞋一样，但不用一位一位的去循环public class BigMode {
public static void main(String[] args) {
String s = "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789839999999999999999999999456789032512847890120347141049814708971625489371245379999994729748743945389024808078";
int j = 0;
int k = 0;
while (true) {
if (s.length() > 9) {
int i = Integer.parseInt(s.substring(0, 9));
s = s.substring(9);//此处9位表示最大可以是9亿，因为int最大是20多亿，如果用long，可以再长点
j = i % 7;
if (j != 0) {
s = j + s;
}
} else {
int i = Integer.parseInt(s);
j = i % 7;
break;
}
}
System.out.println("s是否能被7整除" + (j == 0)+",余数："+j);
}
}

Answer 43

        String s = "13566413132641313134154631313454645654456513546496";
        int n = 7;
        int tmp = 0;
        for(int i = 0; i < s.length(); i++){            tmp = (tmp * 10 + Integer.parseInt(s.substring(i, i + 1))) % n;
        }
        System.out.println("余数为：" + tmp);

Answer 44

public static void main(String[] args) { String str = "5673454322654648748998323211231231231231231231231231232145668127348612734128637423123"; int remainder = 0; for (int i = 0; i < str.length(); i += 8) {
String temp;
if (i + 8 < str.length()) {
temp = str.substring(i, i + 8);
} else {
temp = str.substring(i);
}
remainder = Integer.parseInt(remainder + temp) % 7;
} System.out.println(str);
System.out.println("除以7的余数为" + remainder); }