Contents
二次剩余
题目大意
求 x^2\equiv N\pmod p 的解。
typedef long long ll;
typedef pair<ll, ll> pll;
#define mp make_pair
namespace Complex {
ll mod, W, W0;
struct comp {
ll x, y;
comp(ll xx = 0, ll yy = 0) x : xx, y : yy {}
};
comp operator * (comp a, comp b) {
ll tmp1 = (a.x * b.x + a.y * b.y % mod * W) % mod;
ll tmp2 = (a.x * b.y + a.y * b.x) % mod;
return comp(tmp1, tmp2);
}
ll ksm(ll a, ll b, ll p) {
ll ans = 1;
for (ll base = a; b; b >>= 1) {
if(b & 1) ans = ans * base % p;
base = base * base % p;
}
return ans;
}
comp ksm(comp a, ll b, ll p) {
comp t=comp(1,0);
while(b) {
if(b & 1) t = t * a;
b >>= 1; a = a * a;
}
return t;
}
};
pll surplus(ll x, ll p) {
using namespace Complex;
if (!x) return mp(0, 0);
mod = p;
if(ksm(x, (mod-1)>>1, mod) == mod-1) return mp(-1, -1);
while(233) {
W0 = rand() % mod;
W = (W0 * W0 % mod - x + mod) % mod;
if(ksm(W, (mod-1)>>1, mod) == mod-1) break;
}
comp a = ksm(comp(W0, 1), (mod+1)>>1, mod);
return mp(min(a.x, mod-a.x), max(a.x, mod-a.x));
}
// main 函数里面不要忘记 srand((unsigned)time(0));
类欧几里得算法
定义：
\begin{aligned}
f(n)&=\sum^n_{i=0}\left\lfloor\frac{ai+b}{c}\right\rfloor \bmod {998244353}\cr g(n)&=\sum^n_{i=0}i\left\lfloor\frac{ai+b}{c}\right\rfloor \bmod {998244353}\cr h(n)&=\sum^n_{i=0}\left\lfloor\frac{ai+b}{c}\right\rfloor^2 \bmod {998244353}
\end{aligned}
普通类欧
题目大意：
给定 n,a,b,c，求上面的 f(n),g(n),h(n)。
拆开用：
注：这样写过不了模版题
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int P = 998244353;
int inv2 = 499122177, inv6 = 166374059;
// 特别注意！如果n,a,b,c初值处于long long范围，需要：
// typedef __int128 ll;
ll f(ll a, ll b, ll c, ll n);
ll g(ll a, ll b, ll c, ll n);
ll h(ll a, ll b, ll c, ll n);
ll f(ll a, ll b, ll c, ll n) {
if(!n) return (b / c);
if(!a) return (n + 1) * (b / c) % P;
if(a >= c || b >= c)
return ((a/c) * n % P * (n+1) % P * inv2 % P
+ (b/c) * (n + 1) % P + f(a % c, b % c, c, n)) % P;
ll m = (a * n + b) / c;
return (n * m % P - f(c, c - b - 1, a, m - 1) + P) % P;
}
ll g(ll a, ll b, ll c, ll n) {
if (n == 0) return 0;
if (a == 0) return (b / c) * n % P * (n + 1) % P * inv2 % P;
if (a >= c || b >= c)
return ((g(a % c, b % c, c, n) + (a / c) * n % P * (n + 1) % P
* (2 * n + 1) % P * inv6 % P + (b / c) * n % P
* (n + 1) % P * inv2 % P) % P + P) % P;
ll m = (a * n + b) / c;
return ((n * (n + 1) % P * m % P - f(c, c - b - 1, a, m - 1)
- h(c, c - b - 1, a, m - 1)) % P * inv2 % P + P) % P;
}
ll h(ll a, ll b, ll c, ll n) {
if (n == 0) return (b / c) * (b / c) % P;
if (a == 0) return (n + 1) * (b / c) % P * (b / c) % P;
if (a >= c || b >= c)
return (((a / c) * (a / c) % P * n % P * (n + 1) % P
* (2 * n + 1) % P * inv6 % P + (b / c) * (b / c) % P
* (n + 1) % P + (a / c) * (b / c) % P * n % P
* (n + 1) % P + h(a % c, b % c, c, n) + 2 * (a / c) % P
* g(a % c, b % c, c, n) % P + 2 * (b / c) % P
* f(a % c, b % c, c, n) % P) % P + P) % P;
ll m = (a * n + b) / c;
return ((n * m % P * (m + 1) % P - 2 * g(c, c - b - 1, a, m - 1)
- 2 * f(c, c - b - 1, a, m - 1) - f(a, b, c, n)) % P + P) % P;
}
int main() {
int T, n, a, b, c;
scanf("%d", &T);
while(T--) {
scanf("%d%d%d%d", &n, &a, &b, &c);
printf("%lld %lld %lld\n", f(a, b, c, n), h(a, b, c, n), g(a, b, c, n));
}
return 0;
}
合起来写：
#include <bits/stdc++.h>
typedef long long ll;
constexpr int P = 998244353;
constexpr ll inv2 = 499122177;
constexpr ll inv6 = 166374059;
ll f(ll a, ll b, ll c, ll n);
ll g(ll a, ll b, ll c, ll n);
ll h(ll a, ll b, ll c, ll n);
struct Query {
ll f, g, h;
};
Query solve(ll a, ll b, ll c, ll n) {
Query ans, tmp;
if (a == 0) {
ans.f = (n + 1) * (b / c) % P;
ans.g = (b / c) * n % P * (n + 1) % P * inv2 % P;
ans.h = (n + 1) * (b / c) % P * (b / c) % P;
}
else if (a >= c || b >= c) {
tmp = solve(a % c, b % c, c, n);
ans.f = (tmp.f + (a / c) * n % P * (n + 1) % P
* inv2 % P + (b / c) * (n + 1) % P) % P;
ans.g = (tmp.g + (a / c) * n % P * (n + 1) % P
* (2 * n + 1) % P * inv6 % P + (b / c)
* n % P * (n + 1) % P * inv2 % P) % P;
ans.h = ((a / c) * (a / c) % P * n % P * (n + 1) % P
* (2 * n + 1) % P * inv6 % P + (b / c) * (b / c)
% P * (n + 1) % P + (a / c) * (b / c) % P * n % P
* (n + 1) % P + tmp.h + 2 * (a / c) % P * tmp.g
% P + 2 * (b / c) % P * tmp.f % P) % P;
return ans;
}
else {
ll m = (a * n + b) / c;
tmp = solve(c, c - b - 1, a, m - 1);
ans.f = (n * (m % P) % P - tmp.f) % P;
ans.g = (n * (n + 1) % P * (m % P) % P
- tmp.f - tmp.h) % P * inv2 % P;
ans.h = (n * (m % P) % P * ((m + 1) % P) % P
- 2 * tmp.g - 2 * tmp.f - ans.f) % P;
}
(ans.f += P) %= P; (ans.g += P) %= P; (ans.h += P) %= P;
return ans;
}
int main() {
int T, n, a, b, c;
scanf("%d", &T);
while(T--) {
scanf("%d%d%d%d", &n, &a, &b, &c);
Query ans = solve(a, b, c, n);
printf("%lld %lld %lld\n", ans.f, ans.h, ans.g);
}
return 0;
}
题目大意：
求
\sum_{k=1}^{N}((kM)\And M) \bmod (10^9+7)
(1 \le N \le 10^{18}, 1 \le M \le 10^{11})
分析：
可以按位做。判断一个数 x 的第 i 位是不是 1 ，设 a=(x>>(i-1))，b=((x>>i)<<1) ，则 x 的第 i 位等于 a-b 。又当且仅当 M 和 kM 的第 i 位都是 1 时，kM 在这一位贡献 2^{i-1} 。因此：
ans=\sum_{i=1}^{(1<<(i-1))\leq m}[(m>>(i-1))\And 1]\cdot\left(\sum_{k=1}^{N}\left(\left\lfloor\frac{kM}{2^{i-1}}\right\rfloor-2\left\lfloor\frac{kM}{2^{i}}\right\rfloor\right)\right)\cdot 2^{i-1}
两个求和均可用类欧几里得求。注意分子分母的 a,b,c 不能对 P 取模！因此要用 __int128 类型计算！
#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int mod = 1e9 + 7;
const int inv2 = 500000004;
long long n, m;
ll pow2[70];
void init() {
pow2[0] = 1;
for(int i = 1; i < 70; i++) pow2[i] = pow2[i-1] * 2;
}
ll f(ll a, ll b, ll c, ll n) {
if(!n) return (b / c);
if(!a) return (n + 1) * (b / c) % mod;
if(a >= c || b >= c)
return ((a/c) * n % mod * (n+1) % mod * inv2 % mod
+ (b/c) * (n+1) % mod + f(a%c, b%c, c, n)) % mod;
ll m = (a * n + b) / c;
return (n * m % mod - f(c, c - b - 1, a, m - 1) + mod) % mod;
}
int main() {
init();
scanf("%lld%lld", &n, &m);
int ans = 0;
for (int i = 1; pow2[i-1] <= m; i++) {
if(((m >> (i-1)) & 1) == 0) continue;
ll tmp1 = f(m, 0, pow2[i - 1], n);
ll tmp2 = f(m, 0, pow2[i], n) * 2 % mod;
ll tmp3 = pow2[i - 1] % mod;
ans = (ans + (tmp1 - tmp2 + mod) * tmp3 % mod) % mod;
}
printf("%d\n", ans);
return 0;
}
模 2 意义下的类欧
bool f(ll a, ll b, ll c, ll n) {
if (!a) return (((n + 1) & (b / c)) & 1) > 0;
if (a >= c || b >= c) {
ll temp = (n & 1) ? (n + 1) / 2 * n : n / 2 * (n + 1);
return ((a / c * temp + (b / c) * (n + 1) + f(a % c, b % c, c, n)) & 1) > 0;
}
else {
ll m = (a * n + b) / c;
return (((n * m) ^ f(c, c - b - 1, a, m - 1)) & 1) > 0;
}
}
例题：hdu6275（2017CCPC杭州 Mod, Xor and Everything）
题目大意：
求 (n \bmod 1) xor (n \bmod 2) xor \cdots xor (n \bmod (n – 1)) xor (n \bmod n)。
分析：
我们可以按位做。对于从低到高第 k 位（从 0 开始）：
ans=\sum_{i=1}^{n}\left\lfloor \frac{n\bmod i}{2^k}\right\rfloor=\sum_{i=1}^{n}\left\lfloor \frac{n- \left\lfloor\frac{n}{i}\right\rfloor\cdot i}{2^k}\right\rfloor
可以用类欧+整除分块做。注意到式子中含有负号，因此我们继续化简：
\begin{aligned}
ans&=\sum_{u=i}^{j}\left\lfloor \frac{n- \left\lfloor\frac{n}{i}\right\rfloor\cdot u}{2^k}\right\rfloor\cr &=\sum_{u=i-j}^{0}\left\lfloor \frac{n- \left\lfloor\frac{n}{i}\right\rfloor\cdot (u+j)}{2^k}\right\rfloor\cr &=\sum_{u=0}^{j-i}\left\lfloor \frac{n- \left\lfloor\frac{n}{i}\right\rfloor\cdot (-u+j)}{2^k}\right\rfloor\cr &=\sum_{u=0}^{j-i}\left\lfloor \frac{n- j\left\lfloor\frac{n}{i}\right\rfloor+u\left\lfloor\frac{n}{i}\right\rfloor}{2^k}\right\rfloor\cr
\end{aligned}
由于整除分块中，
\left\lfloor\frac{n}{i}\right\rfloor=\left\lfloor\frac{n}{j}\right\rfloor
故：
n- j\left\lfloor\frac{n}{i}\right\rfloor=n\bmod j
这样就转化成了类欧。注意整除分块的过程中，我们可以一次性把所有位都给算完，即每次求一部分的异或和。同时可以对 [1,3\times 10^7] 之内暴力求。
int main(int argc, const char * argv[]) {
int T; scanf("%d", &T);
while (T--) {
scanf("%lld", &n);
ll ans = 0;
ll x = min(30000000LL, n);
for (ll i = 1; i <= x; i++) ans ^= n % i;
for (ll i = x + 1, j; i <= n; i = j + 1) {
j = n / (n / i);
ll tmp = 0;
ll lim = n / i * (j - i) + n % j;
for (ll k = 1; k <= lim; k <<= 1) {
tmp += f(n / i, n % j, k, j - i) * k;
}
ans ^= tmp;
}
printf("%lld\n", ans);
}
return 0;
}