P1017 题解

ikunTLE · 2025-01-19 18:00:01 · 题解

题目传送门

思路

在本文中，设被除数为 a，除数为 b，商为 q，余数为 r。

首先考虑 R 为正数的情况。将一个十进制数 n 转为二进制，可以用短除法依次取余 2，最后倒序输出即可。这种方法可以将 n 转为任意 R 进制，只需把模数改为 R 即可。

再考虑 R 为负数的情况。基本的除法公式为 \frac{a}{b}=q\cdots r，在这基础上推出 a=b\times q+r=b\times(q+1)+r-b。

当 b<0 且 \lvert r\rvert<\lvert b\rvert 时，r-b\ge0。所以若 b<0，更改 q\gets q+1，r\gets r-b 即可。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
int a,b;
void dfs(int x){
    if(!x)
        return;
    int q=x/b,r=x%b;
    if(r<0)
        ++q,r-=b;
    dfs(q);//倒序输出
    if(r<10)
        putchar(r+'0');
    else putchar(r+'A'-10);
    return;
}
int main(){
    a=read(),b=read();
    printf("%d=",a);
    dfs(a);
    printf("(base%d)\n",b);
    return 0;
}