2022 02 27 基础数论
Summation of Four Primes¶
// 任一大于2的偶数都可写成两个素数之和
#include <bits/stdc++.h>
using namespace std;
const int N = 10000000 + 10;
int n, cnt;
int prime[N / 2];
bool v[N];
int main() {
v[0] = 1, v[1] = 1;
for (int i = 1; i < N; ++i) {
if (!v[i]) prime[++cnt] = i;
for (int j = 1; j <= cnt && i * prime[j] < N; ++j) {
v[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
while (scanf("%d", &n) == 1) {
if (n < 8)
puts("Impossible.");
else {
if (n % 2 == 0) {
n -= 4;
for (int i = 1; i <= cnt; ++i) {
if (!v[prime[i]] && !v[n - prime[i]]) {
printf("2 2 %d %d\n", prime[i], n - prime[i]);
break;
}
}
} else {
n -= 5;
for (int i = 1; i <= cnt; ++i) {
if (!v[prime[i]] && !v[n - prime[i]]) {
printf("2 3 %d %d\n", prime[i], n - prime[i]);
break;
}
}
}
}
}
}Primed Subsequence¶
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000021;
ll n, cnt, prime[N / 2], t;
bool v[N];
const int M = 10010;
ll a[M], cumsum[M];
int main() {
v[0] = v[1] = 1;
for (int i = 2; i < N; ++i) {
if (!v[i]) prime[++cnt] = i;
for (int j = 1; j <= cnt && i * prime[j] < N; ++j) {
v[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
scanf("%lld", &t);
for (int i = 1; i <= t; ++i) {
int found = 0;
scanf("%lld", &n);
for (int j = 1; j <= n; ++j) scanf("%lld", a + j);
for (int j = 1; j <= n; ++j) cumsum[j] = a[j] + cumsum[j - 1];
for (int j = 2; j <= n; ++j) { // 枚举区间长度
for (int k = 1; k <= n - j + 1; ++k) { // 枚举区间左端点
if (v[cumsum[k + j - 1] - cumsum[k - 1]] == 0) {
printf("Shortest primed subsequence is length %d:", j);
for (int p = k; p <= k + j - 1; ++p) printf(" %d", a[p]);
puts("");
found = 1;
break;
}
}
if (found) break;
}
if (!found) printf("This sequence is anti-primed.\n");
}
}Factorial¶
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int tc;
cin >> tc;
while (tc--) {
ll n;
cin >> n;
int ans = 0;
while (n) {
ans += n / 5;
n /= 5;
}
cout << ans << endl;
}
}Hankson 的趣味题¶
/**
* 枚举 0 到 sqrt(b1) 中 b1 的因子(也就是 x )，
* 如果这个数是 a1 的整数倍，并且满足
* gcd(x/a1, a0/a1) = 1
* gcd(b1/b0, b1/x) = 1
* 则ans++
*
* ref: https://blog.csdn.net/nuclearsubmarines/article/details/77603154
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
int tc;
cin >> tc;
while (tc--) {
int a0, a1, b0, b1;
cin >> a0 >> a1 >> b0 >> b1;
int p = a0 / a1, q = b1 / b0, ans = 0;
for (int x = 1; x <= b1 / x; ++x) {
if (b1 % x == 0) {
if (x % a1 == 0 && __gcd(x / a1, p) == 1 && __gcd(q, b1 / x) == 1)
ans++;
int y = b1 / x;
if (x == y) continue;
if (y % a1 == 0 && __gcd(y / a1, p) == 1 && __gcd(q, b1 / y) == 1)
ans++;
}
}
cout << ans << endl;
}
}裴蜀定理¶
已知：\(\sum_{i=1}^n a_i x_i = f\)，其中\(a_i, x_i, f \in Z\)
求证：此方程有解的充要条件是\(\gcd(a_1, a_2, \ldots, a_n) | f\)，其中\(n \in N^+ \and n \in [2, +\infty)\)
证明：
必要性：
设\(\gcd(a_1, a_2, \ldots, a_n) = k\)，则\(k|a_1, k|a_2, \ldots, k | a_n\)
\(\therefore k | \sum_{i=1}^na_ix_i\)
即\(\gcd(a_1, a_2, \ldots, a_n) | f\)
充分性：
使用数学归纳法
显然\(n=2\)时成立
假设\(n=x\)时成立，考虑\(n=x+1\)时的情况
设\(\sum_{i=1}^na_i = S\)，\(\gcd(a_1, a_2, \ldots, a_n) = k\)，
总存在一对整数\((N, M)\)使得\(N\times S + M \times a_{x+1} = \gcd(k, a_{x+1})\)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
int ans;
cin >> n >> ans;
ans = abs(ans);
for (int i = 0; i < n - 1; ++i) {
int x;
cin >> x;
x = abs(x);
ans = __gcd(x, ans);
}
cout << ans << endl;
}Product 1 Modulo N¶
#include <bits/stdc++.h>
using namespace std;
bool ok[100005];
// 结果中所有数字都必须要与n互质
int main() {
int n;
scanf("%d", &n);
long long prod = 1;
for (int i = 1; i < n; i++) {
if (__gcd(n, i) == 1) {
ok[i] = 1;
prod = (prod * i) % n;
}
}
if (prod != 1) ok[prod] = 0;
printf("%d\n", count(ok + 1, ok + n, 1));
for (int i = 1; i < n; i++) {
if (ok[i]) printf("%d ", i);
}
}Power Products¶
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using VIP = vector<pair<int, int>>;
VIP factor(int n, int k) {
map<int, int> F;
for (int i = 2; i * i <= n; i++)
while (n % i == 0)
n /= i, F[i]++;
if (n > 1)
F[n]++;
VIP L;
for (const auto &p : F)
if (p.second % k)
L.push_back({p.first, p.second % k});
return L;
}
int main() {
int N, K;
cin >> N >> K;
map<VIP, int> FM;
for (int i = 0, a; i < N; i++)
cin >> a, FM[factor(a, K)]++;
LL ans = 0;
for (const auto &fm : FM) {
VIP f2 = fm.first;
LL fc = fm.second;
for (auto &p : f2)
p.second = K - p.second;
if (FM.count(f2))
ans += fm.first == f2 ? (fc * (fc - 1)) : (fc * FM[f2]);
}
cout << ans / 2 << endl;
}小凯的疑惑¶
#include <iostream>
using namespace std;
int main() {
long long a, b;
cin >> a >> b;
cout << a * b - a - b << endl;
return 0;
}同余方程¶
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
void ex_gcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1, y = 0;
return;
}
ex_gcd(b, a % b, y, x);
y -= (a / b) * x;
}
ll a, b;
int main() {
cin >> a >> b;
if (a > b) swap(a, b);
ll x, y;
ex_gcd(a, b, x, y);
if (x > 0) {
swap(a, b);
swap(x, y);
}
ll tmp = (-x) / b;
x = x + tmp * b;
y = y - tmp * a;
while (x < 0) x = x + b, y = y - a;
while (x > 0) x = x - b, y = y + a;
ll ans;
ll xx2 = x + b;
ans = a * (xx2 - 1) + b * (y - 1);
cout << ans - 1 << endl;
return 0;
}Divisors¶
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int NN = 1e5 + 4;
bool isPrime[NN];
vector<int> Primes;
void sieve() {
fill_n(isPrime, NN, true), isPrime[1] = false;
for (LL i = 2; i < NN; i++) {
if (!isPrime[i])
continue;
Primes.push_back(i);
for (LL j = i * i; j < NN; j += i)
isPrime[j] = false;
}
}
LL divCnt(int x) {
LL c = 1, xb = x;
for (size_t i = 0; i < Primes.size() && Primes[i] < xb; i++) {
int p = Primes[i], pc = 0;
while (x % p == 0)
x /= p, ++pc;
c *= pc + 1;
}
if (x > 1)
c *= 2;
return c;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
sieve();
int T;
cin >> T;
for (int L, U; T--;) {
cin >> L >> U;
LL ans = 1, ans_c = -1;
for (int x = L; x <= U; x++) {
LL c = divCnt(x);
if (c > ans_c)
ans = x, ans_c = c;
}
printf("Between %d and %d, %lld has a maximum of %lld divisors.\n", L, U,
ans, ans_c);
}
return 0;
}约数研究¶
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int n;
cin >> n;
LL ans = 0;
for (int i = 1; i <= n; i++)
ans += n / i; // i的倍数有n/i个,是 n/i个数字的约数
cout << ans << endl;
return 0;
}森林里的树¶
#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for (int i = (a); i < (b); ++i)
typedef long long LL;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXA = 2000 + 4;
LL Phi[MAXA];
void init() {
fill_n(Phi, MAXA, 0);
Phi[1] = 1;
_for(i, 2, MAXA) if (Phi[i] == 0) {
for (LL j = i; j < MAXA; j += i) {
LL &pj = Phi[j];
if (pj == 0)
pj = j;
pj = pj / i * (i - 1);
}
}
}
int main() {
init();
for (int A, B; scanf("%d%d", &A, &B) == 2 && A && B;) {
LL P = 0;
for (int x = 1; x <= A; x++) {
int k = B / x;
P += k * Phi[x];
for (int y = k * x + 1; y <= B; y++)
if (gcd(x, y) == 1)
P++;
}
double ans = 4 * (P + 1);
LL N = 4LL * A * B + 2LL * A + 2LL * B;
printf("%.7lf\n", ans / N);
}
return 0;
}GCD Extreme¶
#include <cstdio>
#include <cstring>
const int NN = 4000000;
typedef long long LL;
int phi[NN + 1];
void phi_table(int n) {
for (int i = 2; i <= n; i++)
phi[i] = 0;
phi[1] = 1;
for (int i = 2; i <= n; i++)
if (!phi[i])
for (int j = i; j <= n; j += i) {
if (!phi[j])
phi[j] = j;
phi[j] = phi[j] / i * (i - 1);
}
}
LL S[NN + 1], f[NN + 1];
int main() {
phi_table(NN);
memset(f, 0, sizeof(f)); // !"#f
for (int i = 1; i <= NN; i++)
for (int n = i * 2; n <= NN; n += i)
f[n] += i * phi[n / i];
S[2] = f[2]; // !"#S
for (int n = 3; n <= NN; n++)
S[n] = S[n - 1] + f[n];
for (int n; scanf("%d", &n) == 1 && n;)
printf("%lld\n", S[n]);
return 0;
}Diluc and Kavya¶
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
using IPair = pair<int, int>;
LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a % b); }
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T, N;
cin >> T;
string S;
while (T--) {
cin >> N >> S;
map<IPair, int> M;
for (int i = 0, k = 0, d = 0; i < N; i++) {
k += S[i] == 'K', d += S[i] == 'D';
int g = gcd(k, d);
cout << ++M[{k / g, d / g}] << " ";
}
cout << endl;
}
return 0;
}Orac and LCM¶
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a % b); }
LL ga, s;
void update() {
LL g = gcd(ga, s);
s = ga / g * s, ga = g;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int n;
cin >> n >> ga >> s, update();
for (int i = 2, a; i < n; i++)
cin >> a, s = gcd(s, a), update();
cout << s << endl;
}The number of pairs¶
#include <bits/stdc++.h>
using namespace std;
const int K = 2e7 + 4;
int P[K], C[K];
int main() {
for (int i = 2; i < K; ++i) { // 筛法,线性筛加速
int &p = P[i]; // 最小素因子
if (p == 0) // 素数
for (int j = i; j < K; j += i)
if (P[j] == 0)
P[j] = i;
}
for (int k = 2; k < K; ++k) {
int p = P[k], j = k / p;
C[k] = C[j] + (p != P[j]);
}
int t, c, d, x, ans;
scanf("%d", &t);
while (t--) {
scanf("%d%d%d", &c, &d, &x), ans = 0;
for (int g = 1; g * g <= x; ++g)
if (x % g == 0) { // 枚举x的约数g
int k = x / g + d;
if (k % c == 0)
ans += 1 << C[k / c];
if (g * g == x)
continue;
k = g + d;
if (k % c == 0)
ans += 1 << C[k / c];
}
printf("%d\n", ans);
}
}A Horrible Poem¶
#include <bits/stdc++.h>
using namespace std;
const int NN = 5e5 + 4, x = 263;
typedef unsigned long long ULL;
typedef long long LL;
ULL XP[NN];
void initXP() {
XP[0] = 1;
for (size_t i = 1; i < NN; i++)
XP[i] = x * XP[i - 1];
}
template <size_t SZ> struct StrHash {
size_t N;
ULL H[SZ];
void init(const char *pc, size_t n = 0) {
if (XP[0] != 1)
initXP();
if (n == 0)
n = strlen(pc);
N = n, H[N] = 0;
for (int i = N - 1; i >= 0; --i)
H[i] = pc[i] - 'a' + 1 + x * (H[i + 1]);
}
void init(const string &S) { init(S.c_str(), S.size()); }
inline ULL hash(size_t i, size_t j) { // hash[i, j]
return H[i] - H[j + 1] * XP[j - i + 1];
}
inline ULL hash() { return H[0]; }
};
StrHash<NN> hs;
char S[NN];
int lastP[NN], primes[NN], pCnt;
void sieve(int N) {
pCnt = 0;
fill_n(lastP, N, 0);
int *P = primes;
for (int i = 2; i < N; ++i) {
int &l = lastP[i]; // i的最小素因子
if (l == 0)
l = i, P[pCnt++] = i; // i是素数
for (int j = 0; j < pCnt && P[j] <= l && P[j] * i < N; ++j)
lastP[i * P[j]] = P[j]; // i*p的最小素因子是p
}
}
int find_rep(int a, int b) {
int L = b - a + 1, xl = L;
while (xl > 1) {
int p = lastP[xl]; // 尝试每一个素因子
if (hs.hash(a, b - L / p) == hs.hash(a + L / p, b))
L /= p;
xl /= p;
}
return L;
}
int main() {
int n, q;
S[0] = '|';
scanf("%d%s%d", &n, S + 1, &q);
hs.init(S, n + 1), sieve(n + 1);
for (int i = 0, a, b; i < q; i++)
scanf("%d%d", &a, &b), printf("%d\n", find_rep(a, b));
return 0;
}猜数字¶
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define _all(i, a, b) for (int i = (a); i <= (int)(b); ++i)
int N;
LL A[20], B[20];
void exgcd(LL a, LL b, LL &x, LL &y) {
b == 0 ? (x = 1, y = 0) : (exgcd(b, a % b, y, x), y -= a / b * x);
}
LL mul(initializer_list<LL> xs, LL mod) {
unsigned long long m = 1;
for (LL x : xs)
(m *= x) %= mod;
return m;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> N;
_all(i, 1, N) cin >> A[i];
LL ans = 0, M = 1;
_all(i, 1, N) {
LL &b = B[i], &a = A[i];
cin >> b, a = (a % b + b) % b, M *= b;
}
for (int i = 1; i <= N; ++i) { // 中国剩余定理
LL b = B[i], w = M / B[i], x, y;
exgcd(w, b, x, y), x = (x % b + b) % b;
(ans += mul({w, x, A[i]}, M)) %= M;
}
cout << ans << endl;
return 0;
}
最后更新:
2023-01-31