2019 ICPC Greater New York Region I - RationalBase（思维+进制转换）
题目链接
题目大意
给出两个质数 p 、 q p、q p、q，将一个十进制数写成 a 0 + a 1 ∗ ( p q ) + a 2 ∗ ( p q ) 2 + . . . + a m ∗ ( p q ) m a_0+a_1*(\frac{p}{q})+a_2*(\frac{p}{q})^2+...+a_m*(\frac{p}{q})^m a0+a1∗(qp)+a2∗(qp)2+...+am∗(qp)m，实际上就是求十进制数的 ( p q ) (\frac{p}{q}) (qp)进制表示
解题思路
第一眼以为需要浮点数取模 f m o d ( ) fmod() fmod()，后来发现把 p q \frac{p}{q} qp当成一个浮点数是行不通的。还是自己思维太死板：此题解法和一般的进制转换问题大致相同，只不过每次总数不仅要除以 p p p还要乘上 q q q，才能逐位取出系数
- n = a 0 + ( p q ) ∗ ( a 1 + a 2 ∗ ( p q ) + . . . ) n = a_0 + (\frac{p}{q})*(a_1 + a_2*(\frac{p}{q}) + ...) n=a0+(qp)∗(a1+a2∗(qp)+...)
- a 0 = n % p a_0 = n \% p a0=n%p， n n n对 p p p取模就可以取出每一位系数，剩下 a 1 + a 2 ∗ ( p q ) + . . . = ( n − a 0 ) ∗ ( p q ) a_1 + a_2*(\frac{p}{q}) + ... = (n - a_0)*(\frac{p}{q}) a1+a2∗(qp)+...=(n−a0)∗(qp)
- 然后把总数乘 q q q再除以 p p p就可以取下一位
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;
unordered_map<int,char> mp;
void init(){
for(int i=0;i<=9;i++){
mp[i]=i+'0';
}
for(int i=0;i<=25;i++){
mp[i+10]='A'+i;
}
for(int i=0;i<=25;i++){
mp[i+36]='a'+i;
}
/*for(int i=0;i<=61;i++)
cout<<mp[i]<<endl;*/
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll p,q,n;
cin>>p>>q>>n;
string ans="";
init();
while(n){
int x=n%p;
ans+=mp[x];
n/=p;
n*=q;
}
for(int i=ans.size()-1;i>=0;i--)
cout<<ans[i];
cout<<endl;
return 0;
}