#421 Div1 C

题意

在 (0, n) 和 (m, 0) 处各有一个装置，从起始点(0, 0)出发，首先走短路到 (m, 0) 拿起装置回到起始点，再去 (0, n) 处拿起装置回到起始点。当 (m, 0) 处的装置被触碰后，对于后面所有时刻，如果存在某一时刻有一点 (x, y) 和其余两个装置的位置三点组成的三角形面积为s，则计数加1，求最终计数。

分析

对于状态 1，即从 \((m, 0)\) 移动到 \((0, 0)\) 的过程，设在 x 轴上移动的坐标为 \((k, 0)\) ，设任意点坐标 \((x, y)\) ，则有 \(((0, n) - (k, 0)) \times ((x, y) - (k, 0)) = 2 * s\) ，作向量叉乘运算。有\(|k*y + n*x - n*k| = 2*s\)，如果要求 (x, y) 有整数解，则要求 \(gcd(k, n)|2*s (1 \leq k \leq m)\)，对 \(n, k, 2*s\) 分解质因子，设质因子的个数分别为 \(ni, ki, si\) ，如果要满足条件，则对于所有质因子有 \(min(ni, ki) \leq si\)，如果 \(ni \leq si\)，则 \(ki\) 没有限制，如果 \(ni > si\)，则 \(ki \leq si\)，可以直接考虑 \(ni > si， ki = si + 1\) 的情况，只要是\(p^{si+1}\)的倍数都是不符合条件，而剩下的都是符合条件的。可以用容斥原理去求。
对于状态 2，第一个装置已经在原点\((0, 0)\)了，而第二个装置的位置为\((0, k)\)，设任意点坐标 \((x, y)\)，向量叉乘运算，有 \((0, k)\times(x, y) = 2*s\)，即\(|k*x|=2*s\)，对于 \(1 \leq k \leq n\)，求 \(k\) 为 \(2*s\) 因子的个数，找到\(2*s\)的素因子及个数，利用 DFS 求解。

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 5;

ll a[3]; // n m s

ll ans;

int isp[MAXN];

vector<int> prime;

struct factor {

    ll x, cnt;

};

vector<factor> fac;

vector<ll> num;

void init() { // 素数筛

    memset(isp, 0, sizeof isp);

    for(int i = 2; i < MAXN; i++) {

        if(!isp[i]) {

            prime.push_back(i);

            for(ll j = 1LL * i * i; j < (ll)MAXN; j += i) {

                isp[j] = 1;

            }

        }

    }

}

vector<factor> getfac(ll x) { // 筛选出质因子及其个数

    vector<factor> vec;

    for(int i = 0; (ll)prime[i] * prime[i] <= x; i++) {

        int c = 0;

        while(x % prime[i] == 0) {

            c++;

            x /= prime[i];

        }

        if(c) {

            vec.push_back(factor{prime[i], c});

        }

    }

    if(x > 1) {

        vec.push_back(factor{x, 1});

    }

    return vec;

}

void dfs1(int pos, ll val, int cnt) { // 容斥

    if(pos >= (int)num.size()) {

        if(cnt & 1) ans -= a[1] / val;

        else ans += a[1] / val;

        return;

    }

    dfs1(pos + 1, val * num[pos], cnt ^ 1);

    dfs1(pos + 1, val, cnt);

}

void solve1() { // 状态 1

    num.clear();

    fac.clear();

    fac = getfac(a[0]);

    for(int i = 0; i < (int)fac.size(); i++) {

        ll sum = 1;

        for(int j = 0; j < fac[i].cnt; j++) {

            sum *= fac[i].x;

            if(a[2] % sum != 0) {

                num.push_back(sum);

                break;

            }

        }

    }

    dfs1(0, 1, 0);

}

void dfs2(int pos, ll val) {

    if(pos >= (int)fac.size()) {

        ans += (val <= a[0]);

        return;

    }

    ll sum = 1;

    for(int i = 0; i <= fac[pos].cnt; i++) {

        dfs2(pos + 1, val * sum);

        sum *= fac[pos].x;

    }

}

void solve2() { // 状态 2

    fac.clear();

    fac = getfac(a[2]);

    dfs2(0, 1);

}

int main() {

    int T;

    init();

    cin >> T;

    while(T--) {

        ans = 0;

        for(int i = 0; i < 3; i++) {

            a[i] = 1LL;

            for(int j = 0; j < 3; j++) {

                ll x;

                cin >> x;

                a[i] *= x;

            }

        }

        a[2] *= 2;

        solve1();

        solve2();

        cout << ans << endl;

    }

    return 0;

}

巴特西

#421 Div1 C

#421 Div1 C

题意

分析

code

最新文章

热门文章