求“超长整数求余”的算法实现。100分。

Question

函数框架，请大家完善中间的代码：
private int LongIntMod(string p_strNum, int p_intMod)
{
}p_strNum是全整数的字符串，不包含小数。
p_strNum之所以使用字符型，是因为数字非常长，是上百位或者上千位甚至更长的数字字符串。由于运算量很大，大家考虑一下运算效率。

Answer 1

TO:liherun
你说的方法是可行的，可以效率上估计不怎么样。TO:zqd5920
已经百度过了，并已经google过了，无解，故在此发帖。

Answer 2

static void Main(string[] args)
        {
            Console.WriteLine(LongIntMod("11111111111",111112));
            Console.Read();
        }
        static private int LongIntMod(string p_strNum, int p_intMod)
        {            
            if (p_strNum.Length < 11)
                return (Int32)(Convert.ToInt64(p_strNum) % p_intMod);
            Int64 canshu = Convert.ToInt64(p_strNum.Substring(0, 10));
            p_strNum = (canshu % p_intMod + Convert.ToInt32(p_strNum.Substring(10, 1)).ToString() + p_strNum.Substring(11));
            return LongIntMod(p_strNum, p_intMod);
            
        } 

Answer 3

baidu、google无果。估计在这里也没啥好结果了。因为被CSDN牛人撞上你帖子的几率不大

Answer 4

用string代替数字的除法 把数字按顺序放在

Answer 5

TO:nkboy
除数是int型，不过一般都不是1位，一般为两位数或三位数。TO:liherun
除数一般为618,有时取62，请大家再想想还有没别的办法。

Answer 6

liherun 的算法大多数情况下满足条件的 不过存在一个小问题，也就是最后的除数也是10位的且别你截取的10还大 比如你举得例子里面把后面的除数改成1222222222，程序会进入死循环

Answer 7

楼主巧了 之前我做了一个数学题是 把一个数A至另一个数B这中间个自然数依次写下来得到一个多位数例如1到2009得到 123456789.....2009,这个多位数除以9余数是多少?
我用程序写出来了
正好可以用在你那上保证可以
我给你核心代码好了就几行
    private int LongIntMod(string p_strNum)
    {
        int n = p_strNum.Length;
        int jieguo = 0;
        for (int i = 0; i <= n; i++)
        {
            int temp= Convert.ToInt32(p_strNum.Substring(i,1));
            jieguo = (jieguo * 10 + temp) % 9;
        }
        return jieguo;
    } 
LZ我试了好使
呵呵 给我分吧

Answer 8

static void Main(string[] args)
        {
            Console.WriteLine(LongIntMod("1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111", 1111111));
            Console.Read();
        }
        static private int LongIntMod(string p_strNum, int p_intMod)
        {            
            if (p_strNum.Length < 19)
                return (Int32)(Convert.ToInt64(p_strNum) % p_intMod);
            Int64 canshu = Convert.ToInt64(p_strNum.Substring(0, 18));
            p_strNum = (canshu % p_intMod + Convert.ToInt32(p_strNum.Substring(18, 1)).ToString() + p_strNum.Substring(19));
            return LongIntMod(p_strNum, p_intMod);
            
        } 
3000多长度

Answer 9

这个算法的核心for (int i = 0; i <= n; i++) 
        { 
            int temp= Convert.ToInt32(p_strNum.Substring(i,1)); 
            jieguo = (jieguo * 10 + temp) % 9; 
        } 
一个大数你要是算余数 从前往后算例如“1234”先是1和9取余的1然1*10+后面的那位“2”
就是12和9取余 得3 然后3*10+后面的“3”就是33和9取余 对了忘了把“9”改过来应该是p_intMod

Answer 10

private int LongIntMod(string p_strNum) 
    { 
        int n = p_strNum.Length; 
        int jieguo = 0; 
        for (int i = 0; i <= n; i++) 
        { 
            int temp= Convert.ToInt32(p_strNum.Substring(i,1)); 
            jieguo = (jieguo * 10 + temp) % p_intMod; 
        } 
        return jieguo; 
    } 
保证正确

Answer 11

应该不会有低于O(n)的方法了，写了一个凑合能用的。
namespace ConsoleApplication4
{
    class Program
    {
        static void Main(string[] args)
        {
            int k = LongIntMod("123456123456123456123456123456123456123456123456123456", 9);
        }        private static int LongIntMod(string p_strNum, int p_intMod)
        {
            int mod = 0, bitMod = 1;            for (int i = p_strNum.Length - 1; i >= 0; i--)
            {
                int currentNum = p_strNum[i] - '0';
                mod += currentNum * bitMod;
                mod %= p_intMod;
                bitMod = (bitMod * 10) % p_intMod;
            }            return mod;
        }
    }
}

Answer 12

static void Main(string[] args)
        {
            Console.WriteLine(LongIntMod("11111111111",111112));
            Console.Read();
        }
        static private int LongIntMod(string p_strNum, int p_intMod)
        {            
            if (p_strNum.Length < 11)
                return (Int32)(Convert.ToInt64(p_strNum) % p_intMod);
            Int64 canshu = Convert.ToInt64(p_strNum.Substring(0, 10));
            p_strNum = (canshu % p_intMod + Convert.ToInt32(p_strNum.Substring(10, 1)).ToString() + p_strNum.Substring(11));
            return LongIntMod(p_strNum, p_intMod);
            
        } 

Answer 13

21楼和22楼，你们的好像不对吧....int n = p_strNum.Length; 
p_strNum.Length - 1；都说了是超长整数，你还用int获取它的长度，那可以吗........

Answer 14

超过这个长度的字符串，需要4G内存才能存下，所以在32位程序来看这不是问题。
另外string的长度上限应该也不会超过int32。btw，不过21楼的程序应该是有些问题的，这类求余应该是从低位到高位递推，除9是特例了。

Answer 15

liherun
kkkkkkmn
litaoye这三位的都可以用，结分了。其中litaoye是最强的.

Answer 16

Int超长的也够了
去长度 一般没事的
我做的是1到2009的连接都够用
就是123456789101112131415.20082009
这已经很长了

Answer 17

不好意思，又胡说八道了，21楼从高到低的递推是对的，不过程序有个小Bug
for (int i = 0; i <= n; i++)  =》 for (int i = 0; i < n; i++) 
private int LongIntMod(string p_strNum) 
    { 
        int n = p_strNum.Length; 
        int jieguo = 0; 
        for (int i = 0; i < n; i++) 
        { 
            int temp= Convert.ToInt32(p_strNum.Substring(i,1)); 
            jieguo = (jieguo * 10 + temp) % p_intMod; 
        } 
        return jieguo; 
    } 

Answer 18

应该还是kkkkkkmn的更简洁吧，改成这样效率会高一些。        private static int LongIntMod2(string p_strNum, int p_intMod)
        {
            int n = p_strNum.Length;
            int jieguo = 0;            for (int i = 0; i < n; i++)
            {
                int temp = p_strNum[i] - '0';
                jieguo = (jieguo * 10 + temp) % p_intMod;
            }            return jieguo;
        } 

Answer 19

TO:kkkkkkmnStopwatch sw = new Stopwatch();
试一下就知道了，litaoye确实效率是最快的。

Answer 20

一次处理1位同Convert.ToInt64一次处理18位，效率至少是一样的，也许还更高一些，
因为Convert.ToInt64本身也是1位1位处理的，另外求%本身的效率同数字的大小也有一定关系，
大数相对也会慢一些，因此在这方面两个程序的效率也是差不多的。

Answer 21

不好意思 我刚仔细看你的
太自信了
你的循环比我的少
但是你的p_strNum = (canshu % p_intMod + Convert.ToInt32(p_strNum.Substring(18, 1)).ToString() + p_strNum.Substring(19));
是什么意思

Answer 22

delphi代码
  intLen = 3; //截断位数
  interval = 1000;// 这里有intLen个0
自己体会，注释省了，已测试基本正常
const
  p_intMod = 34;
  intLen = 3;
  interval = 1000;procedure TForm1.Button1Click(Sender: TObject);
var
  p_strNum: string;
  ret, vstr, tmpStr: string;
  index: Integer;
  tmpMod: Integer;
  len8: Integer;
begin
  p_strNum := Edit1.Text;
  vstr := rightstr(p_strNum, intLen);
  tmpStr := LeftStr(p_strNum, Length(p_strNum)-intLen);
  index := 1;
  tmpMod := 0;
  while vstr <> '' do
  begin
    len8 := StrToInt(vstr);
    if index > 1 then
      tmpMod := tmpMod + ((len8 mod p_intMod) * Nmod(index-1)) mod p_intMod
    else
      tmpMod := len8 mod p_intMod;
    Inc(index);
    tmpMod := tmpMod mod p_intMod;
    vstr := rightstr(tmpStr, intLen);
    tmpStr := LeftStr(tmpStr, Length(tmpStr)-intLen);
  end;  edit2.Text := IntToStr(tmpMod);
end;function TForm1.Nmod(n: Integer): Integer;var
  i: integer;
begin
  result := 0;
  if n >= 1 then
  begin
    if n = 1 then
      result := interval  mod p_intMod
    else
      result := (Nmod(n-1) * Nmod(1)) mod p_intMod;
  end;
end;