#include <bits/stdc++.h>
int phi (int x) {
int ans = x;
for (int i = 2; i <= x / i; i ++) {
if (x % i == 0) {
ans = ans / i * (i - 1);
while (x % i == 0) x /= i;
}
}
if (x > 1) ans = ans / x * (x - 1);
return ans;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
long long ans = 0;
for (int i = 1; i <= n / i; i ++) {
if (n % i == 0) {
ans += 1ll * n / i * phi (i);
if (i * i != n) ans += 1ll * i * phi (n / i);
}
}
std::cout << ans << '\n';
return 0;
}
活动打卡代码
AcWing 221. 龙哥的问题
活动打卡代码
AcWing 3123. 高精度乘法II
#include <bits/stdc++.h>
using i64 = long long;
const int N = 3e5 + 10;
const double PI = acos(-1);
int n, m;
struct Complex {
double x, y;
Complex operator+ (const Complex& t) const {
return {x + t.x, y + t.y};
}
Complex operator- (const Complex& t) const {
return {x - t.x, y - t.y};
}
Complex operator* (const Complex& t) const {
return {x * t.x - y * t.y, x * t.y + y * t.x};
}
}a[N], b[N];
int rev[N], ans[N], bit, tot;
void FFT (Complex a[], int inv) {
for (int i = 0; i < tot; i ++) {
if (i < rev[i]) {
std::swap (a[i], a[rev[i]]);
}
}
for (int mid = 1; mid < tot; mid <<= 1) {
auto w1 = Complex({cos(PI / mid), inv * sin(PI / mid)});
for (int i = 0; i < tot; i += mid * 2) {
auto wk = Complex({1, 0});
for (int j = 0; j < mid; j ++, wk = wk * w1) {
auto x = a[i + j], y = wk * a[i + j + mid];
a[i + j] = x + y, a[i + j + mid] = x - y;
}
}
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::string A, B;
std::cin >> A >> B;
int n = A.size() - 1, m = B.size() - 1;
for (int i = 0; i <= n; i ++) {
a[i].x = A[n - i] - '0';
}
for (int i = 0; i <= m; i ++) {
b[i].x = B[m - i] - '0';
}
while ((1 << bit) < n + m + 1) {
bit ++;
}
tot = 1 << bit;
for (int i = 0; i < tot; i ++) {
rev[i] = (rev[i >> 1] >> 1) | (i & 1) << (bit - 1);
}
FFT(a, 1), FFT(b, 1);
for (int i = 0; i < tot; i ++) {
a[i] = a[i] * b[i];
}
FFT(a, -1);
int k = 0;
for (int i = 0, t = 0; i < tot || t; i ++) {
t += a[i].x / tot + 0.5;
ans[k ++] = t % 10;
t /= 10;
}
while (k > 1 && !ans[k - 1]) k --;
for (int i = k - 1; i >= 0; i --) {
std::cout << ans[i];
}
return 0;
}
活动打卡代码
AcWing 3122. 多项式乘法
#include <bits/stdc++.h>
using i64 = long long;
const int N = 3e5 + 10;
const double PI = acos(-1);
int n, m;
struct Complex {
double x, y;
Complex operator+ (const Complex& t) const {
return {x + t.x, y + t.y};
}
Complex operator- (const Complex& t) const {
return {x - t.x, y - t.y};
}
Complex operator* (const Complex& t) const {
return {x * t.x - y * t.y, x * t.y + y * t.x};
}
}a[N], b[N];
int rev[N], bit, tot;
void FFT (Complex a[], int inv) {
for (int i = 0; i < tot; i ++) {
if (i < rev[i]) {
std::swap (a[i], a[rev[i]]);
}
}
for (int mid = 1; mid < tot; mid <<= 1) {
auto w1 = Complex({cos(PI / mid), inv * sin(PI / mid)});
for (int i = 0; i < tot; i += mid * 2) {
auto wk = Complex({1, 0});
for (int j = 0; j < mid; j ++, wk = wk * w1) {
auto x = a[i + j], y = wk * a[i + j + mid];
a[i + j] = x + y, a[i + j + mid] = x - y;
}
}
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
for (int i = 0; i <= n; i ++) {
std::cin >> a[i].x;
}
for (int i = 0; i <= m; i ++) {
std::cin >> b[i].x;
}
while ((1 << bit) < n + m + 1) {
bit ++;
}
tot = 1 << bit;
for (int i = 0; i < tot; i ++) {
rev[i] = (rev[i >> 1] >> 1) | (i & 1) << (bit - 1);
}
FFT(a, 1), FFT(b, 1);
for (int i = 0; i < tot; i ++) {
a[i] = a[i] * b[i];
}
FFT(a, -1);
for (int i = 0; i <= n + m; i ++) {
std::cout << int(a[i].x / tot + 0.5) << ' ';
}
return 0;
}
活动打卡代码
AcWing 2702. problem b
#include <bits/stdc++.h>
using i64 = long long;
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
const int N = 50000;
std::vector<int> is_primes(N + 1, 1), mu(N + 1);
is_primes[0] = is_primes[1] = 0;
mu[1] = 1;
std::vector<int> primes;
for (int i = 2; i <= N; i++) {
if (is_primes[i]) {
primes.push_back(i);
mu[i] = -1;
}
for (auto p : primes) {
if (i * p > N) break;
is_primes[i * p] = 0;
if (i % p == 0) break;
mu[p * i] = -mu[i];
}
}
std::vector<int> sum(N + 1);
for (int i = 1; i <= N; i ++) {
sum[i] = sum[i - 1] + mu[i];
}
int _;
std::cin >> _;
while (_ --) {
int a, b, c, d, k;
std::cin >> a >> b >> c >> d >> k;
auto f = [&] (int a, int b) {
a = a / k, b = b / k;
i64 res = 0;
int n = std::min(a, b);
for (int l = 1, r; l <= n; l = r + 1) {
r = std::min({n, a / (a / l), b / (b / l)});
res += 1ll * (sum[r] - sum[l - 1]) * (a / l) * (b / l);
}
return res;
};
std::cout << f(b, d) - f(a - 1, d) - f(b, c - 1) + f(a - 1, c - 1) << '\n';
}
return 0;
}
活动打卡代码
AcWing 196. 质数距离
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define int long long
using i64 = long long;
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
const int N = std::sqrt(2ll << 31 - 1);
std::vector<int> is_primes(N + 1, 1);
std::vector<int> primes;
for (int i = 2; i <= N; i++) {
if (is_primes[i]) {
primes.push_back(i);
}
for (auto p : primes) {
if (i * p > N) break;
is_primes[i * p] = 0;
if (i % p == 0) break;
}
}
int l, r;
while(std::cin >> l >> r) {
std::unordered_set<int> st;
st.insert(1);
for(auto p : primes) {
for(i64 i = std::max((l + p - 1) / p * p, 2 * p); i <= r; i += p) {
st.insert(i);
}
}
int fr = -1;
std::array<i64, 2> dist = {i64(1e18), 0ll};
std::pair<int, int> min = {-1, -1}, max = {-1, -1};
for(int i = l; i <= r; i ++) {
if(!st.count(i)) {
if(fr == -1) fr = i;
else {
int d = i - fr;
if(d < dist[0]) min = {fr, i}, dist[0] = d;
if(d > dist[1]) max = {fr, i}, dist[1] = d;
fr = i;
}
}
}
if(dist[0] >= 1e18 / 2) {
std::cout << "There are no adjacent primes.\n";
} else {
std::cout << min.first << "," << min.second << ' ';
std::cout << "are closest, ";
std::cout << max.first << "," << max.second << ' ';
std::cout << "are most distant.\n";
}
}
return 0;
}
活动打卡代码
AcWing 1293. 夏洛克和他的女朋友
#include <bits/stdc++.h>
using i64 = long long;
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, max = 1;
std::cin >> n;
n ++;
std::vector<int> st(n + 1);
for(int i = 2; i <= n; i ++) {
if(st[i] == 0) {
st[i] = 1;
for(int j = i + i; j <= n; j += i)
st[j] = 2, max = std::max(max, st[j]);
}
}
std::cout << max << '\n';
for(int i = 2; i <= n; i ++)
std::cout << st[i] << ' ';
return 0;
}
