Matthew192 @ 2022-04-26 15:36:27
试一试今天新写的模版,看看能不能用。大家可以参考使用哦~
#include <bits/stdc++.h>
using namespace std;
inline namespace fastmath{
typedef long long ll;
typedef unsigned long long ull;
typedef __uint128_t L;
inline ll ABS(ll n);
inline ll ADD(ll a, ll b);
inline ll SUB(ll a, ll b);
inline ll MUL(ll a, ll b);
inline ll DIV(ll a, ll b);
inline ll POW(ll a, ll b, ll mod);
inline ull MOD(ull a, ull b);
inline ll ABS(ll n){
return (n ^ (n >> 63)) - (n >> 63);
}
inline ll ADD(ll a, ll b){
if (a < 0 && b < 0){
return -ADD(-a, -b);
}
if (a < 0){
return SUB(b, -a);
}
if (b < 0){
return SUB(a, -b);
}
while (b > 0){
ll carry = a & b;
a ^= b;
b = carry << 1;
}
return a;
}
inline ll SUB(ll a, ll b){
if (a < 0 && b < 0){
return -SUB(-a, -b) + 1;
}
if (a < 0){
return ADD(-a, b);
}
if (b < 0){
return ADD(a, -b);
}
while (b != 0){
ll carry = (~a) & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
inline ll MUL(ll a, ll b){
ll x = ABS(a), y = ABS(b), res = 0;
bool neg = false;
if (min(a, b) < 0 && max(a, b) >= 0){
neg = true;
}
while(y > 0){
if ((y & 1) == 1){
res += x;
}
y >>= 1; x <<= 1;
}
if (neg){
return (~(res) + 1);
}
else{
return res;
}
}
inline ll DIV(ll a, ll b){
if (a < 0 && b < 0){
return DIV(-a, -b);
}
if (a < 0){
return -DIV(-a, b);
}
if (b < 0){
return -DIV(a, -b);
}
int tmp = 1, res = 0;
while (b <= a){
b <<= 1;
tmp <<= 1;
}
while (tmp > 1){
b >>= 1;
tmp >>= 1;
if (a >= b){
a -= b;
res += tmp;
}
}
return res;
}
inline ll POW(ll base, ll exponent, ll mod=LLONG_MAX){
ll x = 1;
ll y = base;
while (exponent > 0){
if (MOD(exponent, 2) == 1){
x = MOD((x * y), mod);
}
y = MOD((y * y), mod);
exponent >>= 1;
}
return MOD(x, mod);
}
struct FastMod{
ull b, m;
FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
ull reduce(ull a) {
ull q = (ull)((L(m) * a) >> 64);
ull r = a - q * b;
return r >= b ? r - b : r;
}
};
FastMod F(2);
inline ull MOD(ull a, ull b){
F = FastMod(b);
return F.reduce(a);
}
}
#include <bits/stdc++.h>
using namespace std;
inline namespace FastIO{
const int bufferSize = 1 << 15;
inline namespace FastInput{
// INPUT
char inputBuffer[bufferSize]; int iPosition, iLength;
char next_char(){
if (iPosition == iLength){
iPosition = 0; iLength = fread(inputBuffer, 1, bufferSize, stdin);
if (!iLength) return EOF;
}
return inputBuffer[iPosition++];
}
void read_string(string &x){
char ch; while(isspace(ch = next_char())){};
do {
x += ch;
} while(!isspace(ch = next_char()) && ch!= '\n');
}
template<class T> void read_int(T &x){ // read int OR long long
char ch; int sign = 1;
while (!isdigit(ch = next_char())){
if (ch == '-') sign *= -1;
}
x = ch - '0';
while (isdigit(ch = next_char())){
x = x * 10 + (ch - '0');
}
x *= sign;
}
template<class T, class... Ts> void read_int(T& t, Ts&... ts){
read_int(t); read_int(ts...);
}
}
inline namespace fastOutput{
// OUTPUT (call initO() at start)
char outBuffer[bufferSize], numberBuffer[100]; int outPosition;
void flushOut(){
fwrite(outBuffer, 1, outPosition, stdout);
outPosition = 0;
}
void write_char(char c){
if (outPosition == bufferSize){
flushOut();
}
outBuffer[outPosition++] = c;
}
void write_string(string s){
for (char c : s){
write_char(c);
}
}
template<class T> void write_int(T x, char after = '\0'){
if (x < 0){
write_char('-');
x = x * -1;
}
int length = 0;
for (; x >= 10; x /= 10){
numberBuffer[length ++] = '0' + (x % 10);
}
write_char('0' + x);
for (int i = length - 1; i >= 0; i --){
write_char(numberBuffer[i]);
}
if (after){
write_char(after);
}
}
void initO(){
assert(atexit(flushOut) == 0);
}
}
}
int main(){
initO();
int a, b;
read_int(a, b);
write_int(ADD(a, b), '\n');
return 0;
}
by rxjdasiwzl @ 2022-04-26 16:26:28
@Coros_Trusds 但是他只实现了 long long
四则运算和乘方。
by Matthew192 @ 2022-04-26 16:30:24
在此说明一下:
代码是今天新打的,可(一)能(定)有BUG。
ADD(a, b) = a + b
SUB(a, b) = a - b
MUL(a, b) = a * b
DIV(a, b) = a // b
MOD(a, b) = a % b
POW(a, b) = a ^ b
POW(a, b, c) = a ^ b % c
都适用位运算实现的,所以使用负数的时候可能会出问题。
而且,说一下:虽然位运算复杂度也是O(1),但是会比正常所谓的O(1)要快。一秒钟可能只能进行2亿次加法运算,但是使用位运算可以进行约10亿次(不是我测的数据,有问题别找我)。
by Matthew192 @ 2022-04-26 16:31:40
@ud2_ 减法
SUB(a, b) = a - b
by Matthew192 @ 2022-04-26 16:33:21
@rxjdasiwzl 是的,但是普通的乘法(a*b)也是用相似的逻辑实现的,但是位运算版本可能更快。
就比如说用位运算写的的abs要比平时用的abs快12-13%
by ud2_ @ 2022-04-26 17:03:58
@Matthew192
一秒钟可能只能进行 2 亿次加法运算,但是使用位运算可以进行约 10 亿次。
不知道是哪来的数据。
本地测试结果是单次加、减、按位与、按位或、按位异或一样快,单次乘略慢,但这也只能代表一种 CPU。建议自己测试。
就比如说用位运算写的的 abs 要比平时用的 abs 快 12-13%。
同上,建议自己测试。
by rxjdasiwzl @ 2022-04-26 17:05:04
@Matthew192 请问你测试过自己的模板效率吗,你是严格多一个 log 的复杂度。还是你觉得你比写 C++ 的人更强,他们都想不到这样写代码。
by Cerisier @ 2022-04-26 17:13:33
/jy
by Matthew192 @ 2022-04-26 17:14:48
@rxjdasiwzl MOD重点测试过,因为以前在筛查指数的时候经常用到,其他的都仅供参考。
by Matthew192 @ 2022-04-26 17:15:18
@ud2_ 好的,谢谢
by PrincessQi @ 2022-04-26 17:19:18
还是你觉得你比写 C++ 的人更强,他们都想不到这样写代码。
@rxjdasiwzl 其实你这句话也有一定问题,C++ 自带的东西很多比手写慢吧。