【数学】ABC 319 E

朱雀 2024-03-04 08:04 108阅读 0赞

[E - Bus Stops][]

题意：

![f19239bed77b4ffda13a74736273c59e.png][]

![7d16c61674c24f709d8179e51f99e550.png][]

![de26fd0781a34edcbc336001beb4e021.png][]

思路：

感觉思路比较简单

首先注意到每个询问的范围是1e9，不难想到答案一定存在某个循环节，最后一定是要 %T的

那么问题就在于找到这个循环节是什么

猜想循环节为lcm(p1, p2, p3, ....)

用小数据验证

n = 2的情况：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    constexpr int N = 1e5 + 10;
    constexpr int M = 1e5 + 10;
    constexpr int P = 2600;
    constexpr i64 Inf = 1e18;
    constexpr int mod = 998244353;
    constexpr double eps = 1e-6;
    
    int n, x, y;
    int p[N], t[N];
    int dp[N];
    
    void solve() {
        std::cin >> n >> x >> y;
        for (int i = 1; i <= n - 1; i ++) {
            std::cin >> p[i] >> t[i];
        }
    
        for (int tt = 0; tt < 840; tt ++) {
            int cur = tt;
            for (int i = 1; i <= n - 1; i ++) {
                int w = (p[i] - cur % p[i]) % p[i];
                cur = cur + w + t[i];
            }
            dp[tt] = cur - tt;
        }
    
        int q, m;
        std::cin >> q;
        while(q --) {
            std::cin >> m;
            std::cout << m + x + dp[(m + x) % 840] + y << "\n";
        }
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    
        int t = 1;
    
        while (t--) {
            solve();
        }
        
        return 0;
    }

p1 和 p2的 T = lcm(p1, p2)

p2 和 p3的 T = lcm(p2, p3)

所以该结论易推广

那么只需要枚举起点，最多lcm(p1, p2, p3....)个，然后模拟过程就好了

Code：

[E - Bus Stops]: https://atcoder.jp/contests/abc319/tasks/abc319_e
[f19239bed77b4ffda13a74736273c59e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/64515f6a90e2486cb0162b2b27d428b5.png
[7d16c61674c24f709d8179e51f99e550.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/250343ae69d54302aea592a68cc71714.png
[de26fd0781a34edcbc336001beb4e021.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/b3f9ee4737f14b919f07a9bdc7cecafc.png