C++ 减小常数的技巧

本文主要介绍了如何通过优化输入输出和某类取模来减少程序运行时间的常数因子，并不涉及计算机底层原理。

快速输入和快速输出

使用 getchar 和 putchar 函数

输入：整数

int read(){
	bool flag=true;
	int ch=getchar(),num=0;
	while(ch<48||ch>57){
		if(ch=='-')flag=false;
		ch=getchar();
	}
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	return flag?num:-num;
}

输入：自然数

int read(){
	int ch=getchar(),num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	return num;
}

输出：整数

//递归版
void write(int a){
	if(a<0)putchar('-'),a=-a;
	if(a>=10)write(a/10);
	putchar(a%10|48);
}
//非递归版
void write(int a){
	static int ch[25],cnt=0;
	if(a<0)putchar('-'),a=-a;
	if(a==0)putchar('0');
	while(a)ch[++cnt]=a%10|48,a/=10;
	while(cnt)putchar(ch[cnt--]);
}

输出：自然数

//递归版
void write(int a){
	if(a>=10)write(a/10);
	putchar(a%10|48);
}
//非递归版
void write(int a){
	static int ch[25],cnt=0;
	if(a==0)putchar('0');
	while(a)ch[++cnt]=a%10|48,a/=10;
	while(cnt)putchar(ch[cnt--]);
}

使用 fread 和 fwrite 函数

namespace IO{
	const int ARR_SIZE=1<<20;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
	void getstr(char*str){
		char ch=gc();
		while(ch=='\r'||ch=='\n'||ch==' '||ch=='\t')ch=gc();
		while(ch!='\r'&&ch!='\n'&&ch!=' '&&ch!='\t'&&ch!=EOF)*(str++)=ch,ch=gc();
		*str='\0';
	}
	template<typename T>
	void write(T a){
		static int ch[50],cnt=0;
		if(a==0)pc('0');
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
	void putstr(const char*str){
		while(*str!='\0')pc(*(str++));
	}
}
using IO::read;
using IO::getstr;
using IO::write;
using IO::putstr;

注意事项：

• 使用此方法时，不能同时调用 getchar、putchar、gets、puts、scanf、printf、cin 和 cout 等其他 IO 函数。
• 如果在控制台中输入，需要在末尾加上 EOF（文件末尾标识符，可以按 Ctrl + Z 实现）。
• 如果要退出程序，一定要再执行一次 flush 函数。
  现在销毁 Output_Stream 时会自动刷新缓冲区。
• 注意 input 和 output 数组的大小，不要超过题目的内存限制。
• 输入时注意判断是否是文件末尾，即 gc 函数的返回值是不是 EOF。而且，读入字符串要 在末尾增加 '\0'。

仅包含自然数输入输出

namespace IO{
	const int ARR_SIZE=1<<20;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
	template<typename T>
	void write(T a){
		static int ch[50],cnt=0;
		if(a==0)pc('0');
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
}
using IO::read;
using IO::write;

仅包含自然数输入

namespace IO{
	const int ARR_SIZE=1<<20;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	char input[ARR_SIZE],*si=input,*ti=input;
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
}
using IO::read;

仅包含自然数输出

namespace IO{
	const int ARR_SIZE=1<<20;
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void write(T a){
		static int ch[50],cnt=0;
		if(a==0)pc('0');
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
}
using IO::write;

快速取模

inline int qmod(int x){
	return x+((x>>31)&P);
}

inline ll qmod(ll x){
	return x+((x>>63)&P);
}

传入的 $x$ 应满足 $-P \le x<P$。

举例：对于整数 $a,b \in [0,P)$，加法应该是 qmod(a+b-P)，减法应该是 qmod(a-b)。