同余定理求大整数余数

marting

1.同余定理：(a+b)%c=((a%c)+(b%c))%c

m%n举例：

123 % n =(((1%n*10%n+2%n)%n*10%n)%n+3%n)%n

利用这个性质我们可以将大整数按位分解存入数组，然后循环求出最终余数。

其中求余函数如下：

小结：

简单的看了一下迭代器的使用，迭代器就像指针样字符串迭代器定义：

string a;

#string::iterator tb=a.begin();//此迭代器指向a的第一个元素

#string::iterator te=a.end()-1;//此迭代器指向a最后一个元素，注意，a.end()并不是指向最后一个元素；

#删除函数erase的三种用法：

（1）erase(pos,n); 删除从pos开始的n个字符，比如erase(0,1)就是删除第一个字符
（2）erase(position);删除position处的一个字符(position是个string类型的迭代器)
（3）erase(first,last);删除从first到last之间的字符（first和last都是迭代器）

#还有个append（）函数，是向字符串后面接字符串的。

一个小问题，纠结了我一下午，怎样删除string中特定字符。

因为开始不知道string可以用下标遍历，所以认为只能用迭代器。而迭代器有个问题要注意，用erase删除一个元素后，字符串长度也会减1，迭代器指向的下标相当于没变。

代码如下：

[C++] 纯文本查看 复制代码

int div(string a,int b)  
{  
    int num[1000],i,la;  
    la=a.length();  
    string::iterator t=a.begin();//迭代器，像指针一样指向字符串头  
    for(i=0;i<a.length();i++)  
        num[i]=*(t+i)-48; //将被除数a从字符串转换到数组中  
    int m=0;  
    for(i=0;i<la;i++)  
    {  
        m=(10*m%b+num[i]%b)%b;//同余定理  
    }  
    return m;  
}

[C++] 纯文本查看 复制代码

int main()  
{  
    string a;  
    int num[100];  
    int b,m,i;  
    cin>>a>>b;  
    m=div(a,b);  
    cout<<m<<endl;  
    return 0;  
[font=Consolas,][font=Tahoma,]}   

ynhh

大师也可写出个类似版主的小程序来分享一下啊

aimisiyou

取余运算，看看汇编。