POJ 2305 - Basic remains

算法

原创

发布日期: 2011-12-06

更新日期: 2026-11-06

文章字数: 748

阅读时长: 3 分

阅读次数:

POJ 2305 - Basic remains
Time: 1000MS
Memory: 65536K
难度: 初级
分类: 同余模

0x00 POJ 原题

Description

Given a base b and two non-negative base b integers p and m, compute p mod m and print the result as a base b integer. p mod m is defined as the smallest non-negative integer k such that p = a*m + k for some integer a.

Input

Input consists of a number of cases. Each case is represented by a line containing three unsigned integers. The first, b, is a decimal number between 2 and 10. The second, p, contains up to 1000 digits between 0 and b-1. The third, m, contains up to 9 digits between 0 and b-1. The last case is followed by a line containing 0.

Output

For each test case, print a line giving p mod m as a base-b integer.

Sample Input

2 1100 101
10 123456789123456789123456789 1000
0

Sample Output

10
789

Source

Waterloo local 2003.09.20

0x10 题目概述

在 b 进制下，求 p%m

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

0x20 解题思路

以字符串形式保存 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 时，会超时的。

0x30 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;
}