# [2017-2018 ACM-ICPC Latin American Regional Programming Contest] A. Arranging tiles

### 代码

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define Rep(i, n) for (int i = 1; i <=(n); i++)
#define range(x) begin(x), end(x)

constexpr double EPS = 1e-8;

int fcmp(double x, double y = 0.0) {
if (fabs(x - y) < EPS) return 0;
return x < y ? -1 : 1;
}

typedef double T;
typedef struct pt {
T x, y;
T operator,(pt a) { return x * a.x + y * a.y; }  // inner product
T operator*(pt a) { return x * a.y - y * a.x; }  // outer product
pt operator+(pt a) { return {x + a.x, y + a.y}; }
pt operator-(pt a) { return {x - a.x, y - a.y}; }

pt operator*(T k) { return {x * k, y * k}; }
pt operator-() { return {-x, -y}; }
} vec;

typedef pair<pt, pt> seg;

int n;
int height;

struct polygon {
int width;
vector<pair<int, int>> lpart, rpart;

void init(vector<pair<int, int>>& pts) {
int minx = INT_MAX, maxx = INT_MIN;
for (auto& p : pts) {
height = max(height, p.second);
minx = min(minx, p.first);
maxx = max(maxx, p.first);
}
width = maxx - minx;
for (auto& p : pts) p.first -= minx;
int i = 1;
while (pts[i].second < height) rpart.push_back(pts[i++]);
rpart.push_back(pts[i++]);
while (i < pts.size()) lpart.push_back(pts[i++]);
lpart.push_back(pts[0]);
reverse(range(lpart));
}
} poly[16];

pt getMidPoint(pair<int, int> pt1, pair<int, int> pt2, double y) {
pt a { (double) pt1.first, (double) pt1.second },
b { (double) pt2.first, (double) pt2.second };
vec v = (b - a) * (1.0 / (b.y - a.y));
return a + v * (y - a.y);
}

double max_overlap(polygon& polyl, polygon& polyr) {
vector<pair<int, int>> &lpts = polyl.rpart, &rpts = polyr.lpart;
int ln = lpts.size(), rn = rpts.size(), yn;
vector<int> ys;
{
vector<int> yl(ln), yr(rn);
rep (i, ln) yl[i] = lpts[i].second;
rep (i, rn) yr[i] = rpts[i].second;
set_union(range(yl), range(yr), back_inserter(ys));
yn = ys.size();
}
int lptr = 0, rptr = 0;
double min_dif = 0.0;
rep (i, yn) {
pt lp = getMidPoint(lpts[lptr], lpts[lptr+1], ys[i]),
rp = getMidPoint(rpts[rptr], rpts[rptr+1], ys[i]);
min_dif = max(min_dif, lp.x - rp.x);
while (lptr < ln-1 && lpts[lptr+1].second <= ys[i]) lptr++;
while (rptr < rn-1 && rpts[rptr+1].second <= ys[i]) rptr++;
}
return polyl.width - min_dif;
}

double g[16][16];
double dp[1 << 14][16];

int main() {
scanf("%d", &n);
rep (i, n) {
int k; scanf("%d", &k);
vector<pair<int, int>> pts;
rep (j, k) {
int x, y; scanf("%d%d", &x, &y);
pts.emplace_back(x, y);
}
poly[i].init(pts);
}
rep (i, n) {
rep (j, n) {
if (i == j) continue;
g[i][j] = max_overlap(poly[i], poly[j]);
}
}
while (rem) {
unsigned bit = rem & -rem;
int i = __builtin_ctz(bit);
rep (j, n) {
if (j == i || ((1 << j) & mask) == 0) continue;
}
rem -= bit;
}
} else {
rep (j, n) dp[mask][j] = (j == i ? 0.0 : -1e15);
}
}
double ans = *max_element(range(dp[(1<<n)-1]));
double tot = 0.0;
rep (i, n) tot += poly[i].width;
printf("%.3f\n", tot - ans);
return 0;
}

# [2018 Multi-University Training Contest 10] C. Calculate

### Statement：

Given $1 \leq A, B, C \leq 10^7$, compute

$\sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^C \phi(\gcd(i, j^2, k^3))$

no more than 10 test cases.

### Solution：

Consider the number of triples (i, j, k) such that $\gcd(i, j^2, k^3) = d$, denoted as $f(d)$. By Mobius inversion,

$f(d) = \sum_{i} \mu(i) g(di)$

where $g(d)$ is the number of triples satisfying $d | \gcd(i, j^2, k^3)$, and the answer should be

$\sum_{d=1}^A f(d) \phi(d)$

Now we try to compute $g(d)$:

$g(d) = \sum_{i = 1}^A [d | i] \sum_{j = 1}^B [d | j^2] \sum_{k = 1}^C [d | k^3]$

Let $d = \prod {p_i}^{a_i}$ denote the unique factorization of d. Note that $d | k^n$ whenever $\prod {p_i}^{\lceil a_i / n \rceil} | k$.

Let $h_n(d) = \prod {p_i}^{\lceil a_i / n \rceil}$, which denotes the minimum positive integer whose nth power is divisible by d. Now $g(d)$ could be rewritten as

$g(d) = \lfloor \frac{A}{d} \rfloor \lfloor \frac{B}{h_2(d)} \rfloor \lfloor \frac{C}{h_3(d)} \rfloor$

$\sum_{d=1}^A f(d) \phi(d) = \sum_{d=1}^A \phi(d) \sum_{i} \mu(i) g(di) = \sum_{q = 1}^A g(q) \sum_{ij = q} \mu(i) \phi(j)$

where the Dirichlet convolution $(\mu * \phi)(q) = \sum_{ij = q} \mu(i) \phi(j)$ is multiplicative and thus could be effectively precomputed (along with $h_2$, $h_3$) by the sieve of Euler in linear time. Hence each test case could be done in $O(A)$ time.

### Source Code:

#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
__func__, ##__VA_ARGS__)
#else
# define _debug(...) ((void) 0)
#endif
#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ULL;

namespace sieve {
constexpr int MAXN = 10000007;
bool p[MAXN];
int prime[MAXN], sz;
int pval[MAXN], pcnt[MAXN];
unsigned h2[MAXN], h3[MAXN], phi[MAXN], muphi[MAXN];

void exec(int N = 10000007) {
p[0] = p[1] = 1;

pval[1] = 1;
pcnt[1] = 0;
h2[1] = h3[1] = phi[1] = muphi[1] = 1;

for (int i = 2; i < N; i++) {
if (!p[i]) {
prime[sz++] = i;
for (LL j = i; j < N; j *= i) {
int b = j / i;
pval[j] = i * pval[b];
pcnt[j] = pcnt[b] + 1;
h2[j] = h2[b] * (pcnt[j] % 2 == 1 ? i : 1);
h3[j] = h3[b] * (pcnt[j] % 3 == 1 ? i : 1);
phi[j] = (i == j ? i-1 : phi[b] * i);
muphi[j] = phi[j] - phi[b];
}
}
for (int j = 0; i * prime[j] < N; j++) {
int x = i * prime[j]; p[x] = 1;
if (i % prime[j] == 0) {
pval[x] = pval[i] * prime[j];
pcnt[x] = pcnt[i] + 1;
} else {
pval[x] = prime[j];
pcnt[x] = 1;
}
if (x != pval[x]) {
int b = x / pval[x];
h2[x] = h2[b] * h2[pval[x]];
h3[x] = h3[b] * h3[pval[x]];
muphi[x] = muphi[b] * muphi[pval[x]];
}
if (i % prime[j] == 0) break;
}
}
}
}

int main() {
using namespace sieve;
exec();
int T; scanf("%d", &T);
while (T--) {
unsigned a, b, c; scanf("%d%d%d", &a, &b, &c);
unsigned res = 0;
for (unsigned i = 1; i <= a; i++)
res += muphi[i] * (a / i) * (b / h2[i]) * (c / h3[i]);
printf("%d\n", res & 0x3fffffff);
}
return 0;
}

# 题解：

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define Rep(i, n) for (int i = 1; i <=(n); i++)
#define range(x) begin(x), end(x)

typedef complex<double> pt, vec;
typedef pair<pt, pt> seg;

const double EPS = 1e-8;
int fcmp(double a, double b = 0.0) {
if (fabs(a - b) < EPS) return 0;
return a < b ? -1 : 1;
}

double operator * (pt a, pt b) {
return a.real() * b.imag() - a.imag() * b.real();
}

double operator , (pt a, pt b) {
return a.real() * b.real() + a.imag() * b.imag();
}

inline bool ptOnSeg(pt p, seg s){
vec v1 = s.first - p, v2 = s.second - p;
return fcmp((v1, v2)) <= 0 && fcmp(v1 * v2) == 0;
}

inline pt getIntersection(pt P, vec v, pt Q, vec w) {
return P + v * (w*(P-Q)/(v*w));
}

// -1 outside the polygon
// 0  on the border of the polygon
// 1  inside the polygon
int ptOnPoly(pt p, pt* poly, int n){
//  fprintf(stderr, "(%.7f, %.7f)\n", p);
int wn = 0;
for (int i = 0; i < n; i++){
if (ptOnSeg(p, {poly[i], poly[i+1]})) return 0;
int d1 = fcmp(poly[i].imag() - p.imag()),
d2 = fcmp(poly[i+1].imag() - p.imag()),
k = fcmp((poly[i+1] - poly[i])*(p - poly[i]));
if (k > 0 && d1 <= 0 && d2 > 0) wn++;
if (k < 0 && d2 <= 0 && d1 > 0) wn--;
}
return wn ? 1 : -1;
}

istream& operator >> (istream& lhs, pt& rhs){
double x, y;
lhs >> x >> y;
rhs = {x, y};
return lhs;
}

int n;
vector<pt> poly;
double ans = 0.0;

void attempt(pt a, pt b) {
vector<pt> points;
rep (i, n)
if (fcmp((b-a)*(poly[i]-a)) * fcmp((b-a)*(poly[i+1]-a)) <= 0) {
auto vec1 = b-a, vec2 = poly[i+1] - poly[i];
if (fcmp(vec1 * vec2) == 0) {
points.push_back(poly[i]);
points.push_back(poly[i+1]);
} else {
points.push_back(getIntersection(a, b-a, poly[i], poly[i+1]-poly[i]));
}
}
sort(range(points), [] (pt a, pt b) {
return make_pair(a.real(), a.imag()) < make_pair(b.real(), b.imag());
});
points.resize(unique(range(points), [] (pt a, pt b) {
return fcmp(a.real(), b.real()) == 0 && fcmp(a.imag(), b.imag()) == 0;
}) - points.begin());
double cur = 0.0;
assert(points.size() > 1);
for (int i = 1; i < points.size(); i++) {
if (ptOnPoly((points[i]+points[i-1]) / 2.0, poly.data(), n) >= 0) {
cur += abs(points[i] - points[i-1]);
} else {
cur = 0.0;
if (abs(points.back() - points[i]) <= ans) return;
}
ans = max(ans, cur);
}
}

int main() {
cin >> n; poly.resize(n);
rep (i, n) cin >> poly[i];
poly.push_back(poly[0]);
rep (i, n) {
rep (j, i) {
attempt(poly[i], poly[j]);
}
}
printf("%.8f\n", ans);
return 0;
}