POJ2305-Basic remains

来源:转载

转载请注明出处:優YoU  http://user.qzone.qq.com/289065406/blog/1309151264

 

大致题意:

在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进制就不一定。

 

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

 

 

 

 1 //Memory Time 
2 //256K 32MS
3
4 #include<iostream>
5 #include<string.h>
6 using namespace std;
7
8 const int size=1000; //大数位数
9
10 int main(void)
11 {
12 int n; //进制数
13 while(cin>>n && n)
14 {
15 char* Stra=new char[size+1]; //字符串n进制被减数
16 char* Strb=new char[size+1]; //字符串n进制减数
17 int pa=0; //Stra[]指针
18 int Diga=0,Digb=0; //数字10进制被减数、减数
19
20 cin>>Stra>>Strb;
21
22 for(int j=0;Strb[j];j++) //把n进制字符串减数 转换为 10进制数字减数
23 {
24 Digb*=n;
25 Digb+=Strb[j]-'0';
26 }
27 for(int i=0;Stra[i];i++) //把n进制字符串被减数 转换为 10进制数字被减数
28 {
29 Diga*=n;
30 Diga+=Stra[i]-'0';
31
32 if(Diga>=Digb) //同余模公式,为避免大数计算,进制转化时顺便求模
33 Diga%=Digb;
34 }
35 if(!Diga)
36 cout<<0<<endl;
37 else
38 {
39 while(Diga) //把10进制数字模 转换为 n进制字符串模
40 {
41 Stra[pa++]=Diga%n+'0';
42 Diga/=n;
43 }
44 for(pa--;pa>=0;pa--)
45 cout<<Stra[pa];
46 cout<<endl;
47 }
48
49 delete Stra;
50 delete Strb;
51 }
52 return 0;
53 }

我的所有ACM解题报告:http://user.qzone.qq.com/289065406/blog/1301632863 || 我的CSDN:http://hi.csdn.net/invite.php?u=10114444&c=57929f66dd919f2b || 我的新浪微博:http://weibo.com/lyy289065406 || 我的腾讯微博:http://t.qq.com/lyy289065406 || 我的QQ空间:http://user.qzone.qq.com/289065406 || 我的百度空间:http://hi.baidu.com/you289065406/home || 我的金山网盘:http://www.kuaipan.cn/register/?invite=evpga1


分享给朋友:
您可能感兴趣的文章:
随机阅读: