尝试去掉一些快速乘,仍然不是T就是WA
by fangzichang @ 2022-09-15 15:46:36
贺了第二篇题解的光速乘过了,,,乘法分配律就nm离谱
by fangzichang @ 2022-09-15 15:52:47
建议不要写```#define int long long```这种
主要是有的变量定义是形如```long int a;```的
by cygnus_beta @ 2022-09-15 15:59:19
@[fangzichang](/user/678087) __int128用快读快写
by Hughpig @ 2022-09-15 16:04:38
## 好的龟速乘模板:
```cpp
typedef long long ll;
inline ll mul(ll a, ll b, ll p) { //return (a*b)%p
if (p <= 1000000000) return a * b % p;
else if (p <= 1000000000000ll) return (((a * (b >> 20) % p) << 20) + (a * (b & ((1 << 20) - 1)))) % p;
else {
ll d = (ll)floor(a * (long double)b / p + 0.5);
ll ret = (a * b - d * p) % p;
if (ret < 0) ret += p;
return ret;
}
}
```
by williamwei @ 2022-09-15 16:28:40
这是一个绝妙的龟速乘,是$O(1)$的
by williamwei @ 2022-09-15 16:29:23
没做过这题,但是有个快速乘板子(
```cpp
#define int long long
int mul(int a,int b,int p)
{
int res=(__int128)a*b%p;
return res;
}
```
by q779 @ 2022-09-15 16:45:11