找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 478|回复: 2

[分享] 同余定理求大整数余数

[复制链接]

已领礼包: 20个

财富等级: 恭喜发财

发表于 2017-3-29 16:20:28 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?立即注册

×
本帖最后由 marting 于 2017-3-29 19:50 编辑

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,]}   



0.jpg
0.jpg
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

已领礼包: 6881个

财富等级: 富甲天下

发表于 2017-4-1 11:04:53 | 显示全部楼层
大师也可写出个类似版主的小程序来分享一下啊
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1857个

财富等级: 堆金积玉

发表于 2017-4-5 14:22:25 | 显示全部楼层
取余运算,看看汇编。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|申请友链|Archiver|手机版|小黑屋|辽公网安备|晓东CAD家园 ( 辽ICP备15016793号 )

GMT+8, 2024-3-28 19:26 , Processed in 0.388079 second(s), 35 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表