标签：return gcd int 题解 ll Astronomers CF819D bmod define

CF819D Mister B and Astronomers Solution

目录

• CF819D Mister B and Astronomers Solution
  • 更好的阅读体验戳此进入
    • 题面
    • Solution
    • Code
  • UPD

更好的阅读体验戳此进入

题面

存在一个星星每 $ T $ 秒闪烁一次，存在 $ n $ 个科学家围成一圈循环观测星星，第一个在 $ 0 $ 秒观测，第二个在 $ a_2 $ 秒观测，第三个在 $ a_2 + a_3 $ 秒观测，$ \cdots $ 第一个科学家在 $ a_1 + a_2 + a_3 + \cdots + a_n $ 观测，$ \cdots $。对于 $ t \in [0, T) $，若星星第一次闪烁在 $ t $ 秒，那么第一次观测到这个星星的科学家将会获得 $ 1 $ 的贡献，求每个科学家的贡献。

Solution

首先不难想到，令 $ S = \sum a_i $，第 $ i $ 个科学家观测时间为 $ \sum_{j = 2}^i a_j + kS, k \in \mathbb{N} $，令 $ t_i = \sum_{j = 2}^i a_j $，同时对于 $ T $，假设本次初始时间为 $ \xi $，那么可以认为需要找到第一个满足 $ t_i + kS \equiv \xi \pmod{T} $。

对于后者式子不难发现其为经典的群论套路，即我们发现对于某个科学家的初始点 $ t_i $，可以认为每次模意义下步进 $ S $，此时会构成 $ \gcd(S, T) $ 个环，环长均为 $ \dfrac{T}{\gcd(S, T)} $，或者说每连续 $ \gcd(S, T) $ 个数均属于不同的环。关于这个性质似乎特别显然，不过这里我们也简单证明一下：

显然我们要证明的即为如下式子：

\[\forall i \in [0, T), i \equiv i + \gcd(S, T) \pmod{\gcd(S, T)} \]

\[\forall i \in [0, T), t \in (0, \gcd(S, T)), i + t \not\equiv i \pmod{\gcd(S, T)} \]

证明均显然。

此时我们考虑，对于一个环内的所有科学家，$ \xi $ 为环上某一点的贡献，我们要找到的就是第一个，或者说其减少最少个 $ S $ 遇到的 $ t_i $，这个东西不难想到，对于两个同环科学家 $ t_i, t_j $，且 $ t_j $ 在 $ t_i $ 之后，两者之间模意义下距离了多少个 $ S $ 就代表 $ i $ 的答案由多少。而对于不同环中显然互相无交无关联。

所以我们可以考虑对于一个环内的所有科学家 $ t_1, t_2, \cdots $，我们如果能够按照其在环内的遍历顺序排序，或者说满足 $ t_i $ 之后的 $ t_j $ 一定是 $ t_i $ 经过最小次模意义下加 $ S $ 的操作得到的（这里如何做我们后文再叙），然后遍历一遍，此时对于相邻的 $ t_i \lt t_j $（注意此时的 $ \lt $ 意义是我们重载过的小于号，且两者相邻或 $ i $ 为末尾 $ j $ 为初始）存在：

\[t_i + xS \equiv t_j \pmod{T} \]

转化后得到：

\[Sx + Ty = t_j - t_i \]

并且显然满足 $ \gcd(S, T) \mid t_j - t_i $，满足 exgcd 的限制，注意此时 $ y $ 是任意的，所以仅需求出 $ x $ 的最小非负整数解，其即代表了 $ t_i $ 对应科学家的总贡献，也就是答案。同时注意若环内仅有一个科学家则其贡献直接为 $ \dfrac{T}{\gcd(S, T)} $。

现在我们在将目光移回上文所述的排序过程，考虑发现该限制对应到上述方程的意义就是 $ x $ 最小的解，如果满足 $ S \perp T $ 那么我们是可以通过乘逆元转换为 $ t_i \times S^{-1} \bmod{T} $ 的偏序关系，但本题显然不满足，于是不难想到若其初始时位置为 $ p_i = t_i \bmod{\gcd(S, T)} $，那么一定存在 $ p_i + kS \equiv t_i \pmod{T} $，发现此方程亦为 exgcd 形式，转换为 $ Sx + Ty = t_i - p_i $，求出 $ x $ 的最小非负整数解即可得到其在环中对应的位置，以其为关键字进行排序则一定满足我们上述的偏序关系。而解相同的，即同环模意义下同位置的，不难想到我们优先保留 $ t_i $ 较小的即可，较后的一定为 $ 0 $。

最终复杂度卡在排序和两次 exgcd 上，为 $ O(n \log n) $。

Tips：还有些小细节，观察所有式子发现，对于所有 $ S $ 和 $ t_i $ 都可以并需要进行 $ S \leftarrow S \bmod{T}, t_i \leftarrow t_i \bmod{T} $，这是对答案无影响的。对于在 set 中排除同环模意义下同位置的，可以考虑利用 C++ 特性，重载小于号，使得只保留相同第一关键字中最先加入的，可以证明最先加入的一定最小。

附：好久没写 exgcd 了，简单重推一下吧：

要求 $ ax + by = \gcd(a, b) $。

显然存在 $ bx' + (a \bmod{b})y' = \gcd(b, a \bmod{b}) $。

又 $ \gcd(a, b) = \gcd(b, a \bmod{b}) $。

整理并展开 $ a \bmod b $ 得到 $ ax + by = bx' + (a - \lfloor \dfrac{a}{b} \rfloor \times b)y' $。

则显然有 $ x = y', y = x' - \lfloor \dfrac{a}{b} \rfloor \times y $。

问题规模缩减，不断递归，直到最终 $ \gcd = 0 $ 则回溯 $ x = 1, y = 0 $ 即可。

此时得到任意解，令 $ d = \dfrac{t_j - t_i}{\gcd(S, T)} $，显然整除，则 $ x \leftarrow x \times d, y \leftarrow y \times d $ 即可，同时注意我们想要求得 $ x $ 得最小非负解，发现方程通解为 $ x + k\dfrac{T}{\gcd(S, T)}, y - k\dfrac{S}{\gcd(S, T)} $，以 $ \dfrac{T}{\gcd(S, T)} $ 为模数对 $ x $ 取模转正后求出对应的 $ y $ 即可找到 $ x $ 的最小非负解。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template < typename T = int >
inline T read(void);

int N;
ll S, T;
int A[210000];
int ans[210000];
int gcdv(-1);
struct Node{
    ll v; ll origin; int idx;
    friend const bool operator < (const Node &a, const Node &b){
        return a.v < b.v;
    }
};
unordered_map < int, set < Node > > loops;

void exgcd(ll a, ll b, ll &x, ll &y){
    if(!b)return x = 1, y = 0, void();
    exgcd(b, a % b, x, y);
    int tmp(x);
    x = y, y = tmp - a / b * y;
}
ll CalMnX(ll ti, ll tj){
    ll x, y; ll d = (tj - ti) / gcdv;
    exgcd(S, T, x, y);
    x *= d, y *= d;
    ll P = T / gcdv;
    x = (x % P + P) % P;
    y = (tj - ti - S * x) / T;
    return x;
}

int main(){
    T = read(), N = read();
    for(int i = 1; i <= N; ++i)(S += (A[i] = read())) %= T;
    gcdv = __gcd(S, T);
    loops[0].insert({Node{0, 0, 1}});
    ll cur(0);
    for(int i = 2; i <= N; ++i)
        (cur += A[i]) %= T,
        loops[cur % gcdv].insert(Node{CalMnX(cur % gcdv, cur), cur, i});
    for(auto loop : loops){
        if((int)loop.second.size() == 1){ans[loop.second.begin()->idx] = T / gcdv; continue;}
        for(auto it = loop.second.begin(); it != loop.second.end(); advance(it, 1)){
            auto nxit = it == prev(loop.second.end()) ? loop.second.begin() : next(it);
            ans[it->idx] = CalMnX(it->origin, nxit->origin);
        }
    }
    for(int i = 1; i <= N; ++i)printf("%d%c", ans[i], i == N ? '\n' : ' ');
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2023_02_13 初稿

标签：return,gcd,int,题解,ll,Astronomers,CF819D,bmod,define
From： https://www.cnblogs.com/tsawke/p/17124381.html