[TIOJ] 1538. 1/n? 埃及商人的煩惱
題目連結:http://tioj.infor.org/problems/1538
一個小小的數學題(?,做法很greedy,每次的分母都會是$\lfloor \frac{分母}{分子} \rfloor + 1$,直到自己的分子變成一為止,不過很梗的是本題要寫大數,不然會WA...,所以我就摳了日月卦長的大數模板
一個小小的數學題(?,做法很greedy,每次的分母都會是$\lfloor \frac{分母}{分子} \rfloor + 1$,直到自己的分子變成一為止,不過很梗的是本題要寫大數,不然會WA...,所以我就摳了日月卦長的大數模板
#include <bits/stdc++.h>
using namespace std;
#ifndef SUN_MOON_BIG_INT
#define SUN_MOON_BIG_INT
#define SM_BASE 1000000000
#define SM_BASE_DIGITS 9
/*SM_BASE 0 的個數為SM_BASE_DIGITS*/
#include<vector>
#include<iostream>
#include<iomanip>
#include<string>
#include<utility>/*for pair*/
class bigN{
private:
std::vector<int>s;
char sign;
inline void trim(){
while(!s.empty()&&!s.back())s.pop_back();
if(s.empty())sign=1;
}
inline char cmp(const bigN &v,bool is=1)const{
if(is){
if(sign>v.sign)return 1;
if(sign<v.sign)return -1;
}
char d=sign>0||!is?1:-1;
if(s.size()>v.s.size())return d;
if(s.size()<v.s.size())return -d;
for(int i=s.size()-1;i>=0;i--){
if(s[i]>v.s[i])return d;
if(s[i]<v.s[i])return -d;
}
return 0;
}
/*在private的部分加入以下兩個函數*/
inline std::vector<int> convert_base(const std::vector<int> &a,int old_digits,int new_digits)const{
std::vector<long long> p(std::max(old_digits,new_digits)+1);
p[0]=1;
for(int i=1;i<(int)p.size();++i)p[i]=p[i-1]*10;
std::vector<int> ans;
long long cur=0;
int cur_digits=0;
for (int i=0;i<(int)a.size();++i){
cur+=a[i]*p[cur_digits];
cur_digits+=old_digits;
while(cur_digits>=new_digits){
ans.push_back(cur%p[new_digits]);
cur/=p[new_digits];
cur_digits-=new_digits;
}
}
ans.push_back((int)cur);
while (!ans.empty()&&!ans.back())ans.pop_back();
return ans;
}
inline std::vector<long long> karatsuba(const std::vector<long long> &a,const std::vector<long long> &b)const{
int n=a.size();
std::vector<long long> res(n*2);
if(n<=32){
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
res[i+j]+=a[i]*b[j];
return res;
}
int k=n/2;
std::vector<long long> a1(a.begin(),a.begin()+k);
std::vector<long long> a2(a.begin()+k,a.end());
std::vector<long long> b1(b.begin(),b.begin()+k);
std::vector<long long> b2(b.begin()+k,b.end());
std::vector<long long> a1b1=karatsuba(a1,b1);
std::vector<long long> a2b2=karatsuba(a2,b2);
for(int i=0;i<k;++i)a2[i]+=a1[i];
for(int i=0;i<k;++i)b2[i]+=b1[i];
std::vector<long long> r=karatsuba(a2,b2);
for(int i=0;i<(int)a1b1.size();++i)r[i]-=a1b1[i];
for(int i=0;i<(int)a2b2.size();++i)r[i]-=a2b2[i];
for(int i=0;i<(int)r.size();++i)res[i+k]+=r[i];
for(int i=0;i<(int)a1b1.size();++i)res[i]+=a1b1[i];
for(int i=0;i<(int)a2b2.size();++i)res[i+n]+=a2b2[i];
return res;
}
public:
/*初始化*/
bigN():sign(1){}
bigN(const long long &v){
*this=v;
}
bigN(const std::string &v){
*this=v;
}
/*等於運算子重載*/
inline void operator=(const bigN &v){
sign=v.sign;
s=v.s;
}
inline void operator=(long long v){
sign=1;s.clear();
if (v < 0)sign=-1,v=-v;
for(;v;v/=SM_BASE)s.push_back(v%SM_BASE);
}
inline void operator=(const std::string &v){
sign=1;s.clear();
int len=0;
for(;len<(int)v.size()&&(v[len]=='-'||v[len]=='+');len++)
if(v[len]=='-')sign=-1;
for(int i=v.size()-1;i>=len;i-=SM_BASE_DIGITS){
int x=0;
for(int j=std::max(len,i-SM_BASE_DIGITS+1);j<=i;j++)
x=x*10+v[j]-'0';
s.push_back(x);
}
trim();
}
/*加減運算子重載*/
inline bigN operator+(const bigN &v)const{
if(sign==v.sign){
bigN ans=v;
int len=std::max(s.size(),v.s.size());
for(int i=0,is=0;i<len||is;i++){
if(i==(int)ans.s.size())ans.s.push_back(0);
ans.s[i]+=is+(i<(int)s.size()?s[i]:0);
is=ans.s[i]>=SM_BASE;
if(is)ans.s[i]-=SM_BASE;
}
return ans;
}else return *this-(-v);
}
inline bigN operator-(const bigN &v)const{
if(sign==v.sign){
if(~cmp(v,0)){
bigN ans=*this;
for(int i=0,is=0;i<(int)v.s.size()||is;i++){
ans.s[i]-=is+(i<(int)v.s.size()?v.s[i]:0);
is=ans.s[i]<0;
if(is)ans.s[i]+=SM_BASE;
}
ans.trim();
return ans;
}else return -(v-*this);
}else return *this+(-v);
}
/*乘法運算子重載*/
/*public的部分operator*的函數用以下函數取代*/
inline bigN operator*(const bigN &v)const{
std::vector<int> a6=convert_base(s,SM_BASE_DIGITS,6);
std::vector<int> b6=convert_base(v.s,SM_BASE_DIGITS,6);
std::vector<long long> a(a6.begin(),a6.end());
std::vector<long long> b(b6.begin(),b6.end());
while(a.size()<b.size())a.push_back(0);
while(b.size()<a.size())b.push_back(0);
while(a.size()&(a.size()-1))a.push_back(0),b.push_back(0);
std::vector<long long> c=karatsuba(a,b);
bigN ans;
ans.sign=sign*v.sign;
for(int i=0,carry=0;i<(int)c.size();++i){
long long cur=c[i]+carry;
ans.s.push_back((int)(cur%1000000));
carry=(int)(cur/1000000);
}
ans.s=convert_base(ans.s,6,SM_BASE_DIGITS);
ans.trim();
return ans;
}
/*對整數的乘除做支援運算*/
inline void operator*=(int v){
if(v<0)sign=-sign,v=-v;
for(int i=0,is=0;i<(int)s.size()||is;i++){
if(i==(int)s.size())s.push_back(0);
long long a=s[i]*(long long)v+is;
is=(int)(a/SM_BASE);
s[i]=(int)(a%SM_BASE);
}
trim();
}
inline bigN operator*(int v){
bigN ans=*this;
ans*=v;
return ans;
}
inline void operator/=(int v){
if(v<0)sign=-sign,v=-v;
for(int i=s.size()-1,rem=0;i>=0;i--){
long long a=s[i]+rem*(long long)SM_BASE;
s[i]=(int)(a/v);
rem=a%v;
}
trim();
}
inline bigN operator/(int v){
bigN ans=*this;
ans/=v;
return ans;
}
inline int operator%(int v){
if(v<0)v=-v;
int m=0;
for(int i=s.size()-1;i>=0;i--)
m=(s[i]+m*(long long)SM_BASE)%v;
return m*sign;
}
/*除法,商為first,餘為second*/
inline friend std::pair<bigN,bigN>divmod(const bigN &a,const bigN &b){
int norm=SM_BASE/(b.s.back()+1);
bigN x=a.abs()*norm;
bigN y=b.abs()*norm;
bigN q,r;
q.s.resize(x.s.size());
for(int i=x.s.size()-1;i>=0;i--){
r*=SM_BASE;
r+=x.s[i];
int s1=r.s.size()<=y.s.size()?0:r.s[y.s.size()];
int s2=r.s.size()<=y.s.size()-1?0:r.s[y.s.size()-1];
int d=((long long)SM_BASE*s1+s2)/y.s.back();
r-=y*d;
while(r.cmp(0,1)==-1)r+=y,--d;
q.s[i]=d;
}
q.sign=a.sign*b.sign;
r.sign=a.sign;
q.trim();
r.trim();
return std::make_pair(q,r/norm);
}
inline bigN operator/(const bigN &v)const{
return divmod(*this,v).first;
}
inline bigN operator%(const bigN &v)const{
return divmod(*this,v).second;
}
/*數學指派運算子重載*/
inline void operator+=(const bigN &v){
*this=*this+v;
}
inline void operator-=(const bigN &v){
*this=*this-v;
}
inline void operator*=(const bigN &v){
*this=*this*v;
}
inline void operator/=(const bigN &v){
*this=*this/v;
}
inline void operator%=(const bigN &v){
*this=*this%v;
}
/*比較運算子重載*/
inline bool operator<(const bigN &v)const{
return cmp(v)<0;
}
inline bool operator>(const bigN &v)const{
return cmp(v)>0;
}
inline bool operator<=(const bigN &v)const{
return cmp(v)<=0;
}
inline bool operator>=(const bigN &v)const{
return cmp(v)>=0;
}
inline bool operator==(const bigN &v)const{
return !cmp(v);
}
inline bool operator!=(const bigN &v)const{
return cmp(v)!=0;
}
/*數學運算子重載*/
inline bigN abs()const{
bigN ans=*this;
ans.sign*=ans.sign;
return ans;
}
inline bigN operator-()const{
bigN ans=*this;
ans.sign=-sign;
return ans;
}
/* >>、<<運算子重載 */
friend std::istream& operator>>(std::istream &stream,bigN &v) {
std::string s;
stream>>s;
v=s;
return stream;
}
friend std::ostream& operator<<(std::ostream &stream,const bigN &v) {
if(v.sign==-1)stream<<'-';
stream<<(v.s.empty()?0:v.s.back());
for(int i=(int)v.s.size()-2;i>=0;i--)
stream<<std::setw(SM_BASE_DIGITS)<<std::setfill('0')<<v.s[i];
return stream;
}
/*是否為0*/
inline bool iszero(){
return !s.size()||(s.size()==1&&!s[0]);
}
/*形態重載*/
inline operator std::string(){
std::string ans,x;
if(s.empty())return "0";
if(sign==-1)ans+='-';
int o=s[s.size()-1];
while(o)x+=o%10+'0',o/=10;
for(int i=x.size()-1;i>=0;i--)ans+=x[i];
for(int i=s.size()-2;i>=0;i--){
std::string t;
int p=s[i];
for(int j=0;j<SM_BASE_DIGITS;j++){
t+=p%10+'0';p/=10;
}
for(int j=SM_BASE_DIGITS-1;j>=0;j--)ans+=t[j];
}
return ans;
}
};
#endif
#undef SM_BASE
#undef SM_BASE_DIGITS
inline bigN gcd(bigN,bigN);
class frac{
private:
bigN mu,zhi;
public:
frac(){}
frac(bigN a,bigN b){
bigN g=gcd(a,b);
zhi=a/g;
mu=b/g;
}
frac operator-(const frac& x)const{
bigN g=gcd(x.mu,mu);
return frac(zhi*(x.mu/g)-x.zhi*(mu/g), x.mu*(mu/g));
}
frac operator=(const frac& x){
zhi=x.zhi;mu=x.mu;
return x;
}
bigN getZhi(){return zhi;}
bigN getMu(){return mu;}
};
int main(){
int a,b;cin>>a>>b;
cout<<a<<"/"<<b<<" = ";
frac ff(a,b);
queue<frac> qq;
while(ff.getZhi()!=1){
bigN i=(ff.getMu()/ff.getZhi())+1;
ff=ff-frac(1,i);
qq.push(frac(1,i));
}
qq.push(ff);
bool first=1;
while(!qq.empty()){
frac tp=qq.front();qq.pop();
if(first){
cout<<"("<<tp.getZhi()<<"/"<<tp.getMu()<<")";
first=0;
}else
cout<<"+("<<tp.getZhi()<<"/"<<tp.getMu()<<")";
}
return 0;
}
inline bigN gcd(bigN a,bigN b){
if(b==0)return a;
else return gcd(b,a%b);
}
留言
張貼留言