大数求余

大数求余，除数与被除数都是大数

/*注意几种情况：主要思想是利用减法，一个个反复去减 1. a的len<b的len时候直接返回串a 2. a的len>b的len的时候要把b的长度在尾部补齐，同时要判断补齐后的大小是否还满足a大于b，如果不满足则b后退一个，前面填0 3. a每次操作完要把串前面存在0的地方去掉*/
#include <iostream>
#include <string>
using namespace std;
string divided(string a,string b)
{
    if(a.size()==b.size())
    {
        string temp=a;
        int flag=0;
        int ai=0,bi=0;
        for(int i=a.length()-1;i>=0;i--)
        {
            ai=a[i]-'0'-flag;
            bi=b[i]-'0';
            if(ai<bi)
            {
                flag=1;
                temp[i]=10+ai-bi+'0';
            }
            else
            {
                flag=0;
                temp[i]=ai-bi+'0';
            }
        }
        return temp;        
    }
}
int main()
{
    string a,b;
    string aa,bb;
    bool flag=true;
    while(cin>>a>>b)//合法输入没有判断负数之类的情况
    {
        if((a.size()<b.size())||((a.size()==b.size())&&(a<b)))
        {
            cout<<a<<endl;
            continue;
        }
        aa=a;
        bb=b;
        while((aa.size()>bb.size())||((aa.size()==bb.size())&&(aa>=bb)))
        {
            string aaa;
            int j=aa.size()-bb.size();
            for(int i=0;i<j;i++)
                bb+="0";
            if(aa>bb)
            {
                aa=divided(aa,bb);
                bb=b;
            }
            else if(aa==bb)
            {
                aa="0";
                bb=b;
            }
            else
            {
                bb="0"+bb.substr(0,bb.length()-1);
                aa=divided(aa,bb);
                bb=b;
            }
            while((aa.substr(0,1)=="0")&&(aa.size()>1))
                    aa=aa.substr(1,aa.size()-1);
        }

        cout<<aa<<endl;
    }
    return 0;
}

被除数为大数，除数为int范围

#include<iostream>
#include<string>
using namespace std;
int main()
{
    string str;
    int value;
    while(cin>>str>>value)
    {
        int len=str.size();
        int t=0;
        for (int i = 0; i < len; ++i)
        {
            t*=10;
            t+=str[i]-'0';
            if (t>=value)
            {
                t=t%value;
            }
        }
        cout<<t<<endl;
    }
}

求a的n次方 mod b

//a^Nmod b
//=((a mod b)*a)mod b
#include<iostream>
using namespace std;
int main()
{
    int v1,v2,v3;
    int r=1;
    cin>>v1>>v2>>v3;
    for (int i = 0; i < v2; ++i)
    {
        r=r*v1%v3;
    }
    cout<<r<<endl;
}