[TIOJ] 1538. 1/n? 埃及商人的煩惱

題目連結:http://tioj.infor.org/problems/1538
一個小小的數學題(?，做法很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);
}

留言

張貼留言

這個網誌中的熱門文章

[TIOJ] 1094. C.幼稚國王的獎賞

題目連結: http://tioj.infor.org/problems/1094 這題有三種作法，一種是我看完馬上想到的砍半枚舉後套trie #include <bits/stdc++.h> using namespace std; const int LOG_C = 20; const int N = 30 + 5; inline int two(int x){return 1<<x;} class Trie{ private: static constexpr int MEM = 5000000; struct node{ int lc, rc; node(): lc(0), rc(0){} } nodes[MEM]; int mem_, root; inline int new_node(){ assert(mem_ < MEM); nodes[mem_] = node(); return mem_++; } void insert(int x, int& cur, int d){ if(!cur) cur = new_node(); if(d == -1) return; if(x & two(d)) insert(x, nodes[cur].rc, d-1); else insert(x, nodes[cur].lc, d-1); } int query(int x, int cur, int d){ if(d == -1) return 0; if(x & two(d)) swap(nodes[cur].lc, nodes[cur].rc); int ret = 0; if(nodes[cur].rc) ret = query(x, nodes[cur].rc, d-1) + two(d); else ret = query(x, nodes[cur].lc, d-1); if(x & two(d)) swap(nodes[cur].lc, nodes[cur].rc); return ret; } public: void init(){
閱讀完整內容

[IOJ] 19. 啦啦啦

題目連結: http://ioj.infor.org/problems/19 因為$xor$有神奇(?的性質$a \oplus b = c \Longrightarrow a \oplus c = b$，所以就$O(n)$掃過去建好表，再$O(n)$掃一遍加起來，值得注意的是因為$a \oplus 0 = a$，所以若$x=0$，那要再減掉所有數的個數(自己不能算) #include <stdio.h> void gn(int &_){ _=0;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')_=_*10+c-'0',c=getchar(); } int MiccWan[100000 + 10]; int wayneTu[1000000 + 10] = {0}; int main(){ int t,x; long long edisonhello=0; gn(t);gn(x); for(int i=0;i<t;i++){ gn(MiccWan[i]); wayneTu[MiccWan[i]^x]++; } for(int i=0;i<t;i++){ edisonhello+=wayneTu[MiccWan[i]]; } if(x==0) edisonhello-=t; printf("%lld",edisonhello>>1); return 0; }
閱讀完整內容

[IOJ] 14. 費氏數列問題

題目連結: https://ioj.infor.org/problems/14 由題目可看出這是一個標準的線性遞迴，而居然是線性遞迴的話，那都可以用矩陣乘法搭配快速冪來讓時間複雜度降到$O(m^3 \log_2{(n-m)})$，然後不難發現其要用的$1 \times m$橫矩陣是$\left( \begin{array}{clr} 1 & 1 & \cdots & 1 \end{array} \right)$，而$m \times m$正方形矩陣則是$\left( \begin{array}{clr} k_{1} & 1 & 0 & 0 & \cdots \\ k_{2} & 0 & 1 & 0 & \cdots \\ k_{3} & 0 & 0 & 1 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \\ k_{m} & 0 & 0 & 0 & \cdots \end{array} \right)$至於會溢位的部分則按照題敘，每次在做加法乘法之類的時候都模一次$10^9+7$，因為可以證明先算再模跟先模再算再模都會得到相同的結果的。 #include <stdio.h> #include <algorithm> typedef long long lld; const lld mmdd = 1000000007; lld m1[110][110]={0}; auto aas = new lld [110][110]; lld n,m; void qPow(lld); void matrixTimes(lld[][110],lld[][110],lld[][110]); int main(){ scanf("%lld %lld",&n,&m); for(lld i=0;i<m;i++){ scanf("%lld",&m1[i][0]); if(i+1<m) m1[i][i+1] = 1; }
閱讀完整內容