POJ 2305 - Basic remains


问题描述

在b进制下,求 p%m

其中p为b进制大数1000位以内,m为b进制数9位以内

解题思路

以字符串形式保存p,m

利用进制转换公式先把m逐位转换为10进制,由于m只有9位,因此直接转换用int保存即可。

再利用进制转换公式把p逐位转换为10进制,为了避免处理大数,转换过程中,若出现比m大的时候,则对m取模,继续转换。根据同余模公式知,这是允许的。

此时得到的p值就是 (10进制p)%(10进制m)

p==0 时,直接输出,否则把p逐位转换回去n进制再输出。

n进制的p必须用数组保存,因为10进制的p虽然不是大数,但n进制就不一定。

不要用大数去做,当 p>>m 时,会超时的。

AC 源码

//Memory Time 
//256K   32MS 

#include<iostream>
#include<string.h>
using namespace std;

const int size=1000;   //大数位数

int main(void)
{
    int n; //进制数
    while(cin>>n && n)
    {
        char* Stra=new char[size+1];  //字符串n进制被减数
        char* Strb=new char[size+1];  //字符串n进制减数
        int pa=0;  //Stra[]指针
        int Diga=0,Digb=0;  //数字10进制被减数、减数

        cin>>Stra>>Strb;

        for(int j=0;Strb[j];j++)  //把n进制字符串减数 转换为 10进制数字减数
        {
            Digb*=n;
            Digb+=Strb[j]-'0';
        }
        for(int i=0;Stra[i];i++)  //把n进制字符串被减数 转换为 10进制数字被减数
        {
            Diga*=n;
            Diga+=Stra[i]-'0';

            if(Diga>=Digb) //同余模公式,为避免大数计算,进制转化时顺便求模
                Diga%=Digb;
        }
        if(!Diga)
            cout<<0<<endl;
        else
        {
            while(Diga)  //把10进制数字模 转换为 n进制字符串模
            {
                Stra[pa++]=Diga%n+'0';
                Diga/=n;
            }
            for(pa--;pa>=0;pa--)
                cout<<Stra[pa];
            cout<<endl;
        }

        delete Stra;
        delete Strb;
    }
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 3432 - Count Squares POJ 3432 - Count Squares
POJ 3432 - Count Squares Time: 3000MS Memory: 65536K 难度: 初级 分类: 高效查找法 问题描述POJ2002,把数据规模从 n=1000 修改为 n=2000 就能AC了。 注意这
2011-12-13
下一篇 
POJ 1035 - Spell checker POJ 1035 - Spell checker
POJ 1035 - Spell checker Time: 1000MS Memory: 65536K 难度: 初级 分类: 串 问题描述输入一部字典,输入若干单词 若某个单词能在字典中找到,则输出corret 若某个单词能通过 变
2011-11-21
  目录