2026年 北马其顿编程竞赛 (Macedonian programming contests 2026)

赛事等级： 社区与地区选拔赛 (Community and Regional competition)
内容类型： 竞赛题目 (Competition tasks)

题目名称：疯狂储蓄 (Лудо штедење)

题目描述

你决定开始存钱，并在银行账户中存入了 $x$ 第纳尔，这意味着你的初始余额为 $x$。但你选择的这家银行非常奇怪，账户余额每天都会发生变化。

在存钱后的每一天 $i$ ($1 \le i \le N$)：

• 如果 $i$ 是奇数，余额增加 2 ($x = x + 2$)。
• 如果 $i$ 是偶数，余额减少 1 ($x = x - 1$)。

更特殊的是，如果在任何时刻（增加或减少后），余额 $x$ 变为了一个能被 4 整除的数，那么该余额会立即乘以 $-1$，即 $x = -x$。

你的任务是计算在 $N$ 天之后，你的最终账户余额 $x$ 是多少。

输入格式

• 第一行包含两个整数：$N$ ($1 \le N \le 10^{15}$) 和初始余额 $x$ ($x \le 10^5$)。

注意： 对于 50% 的测试点，$N < 10,000$。

输出格式

• 输出一个整数，代表 $N$ 天后的最终余额 $x$。

限制条件

• 时间限制： 100 毫秒
• 内存限制： 64 MB

样例说明

样例 1： 输入：6 3 输出：-2

• 第 1 天 ($i=1$, 奇数)：$3 + 2 = 5$，$5$ 不能被 4 整除。
• 第 2 天 ($i=2$, 偶数)：$5 - 1 = 4$，$4$ 能被 4 整除 $\rightarrow x = -4$。
• 第 3 天 ($i=3$, 奇数)：$-4 + 2 = -2$，不能被 4 整除。
• 第 4 天 ($i=4$, 偶数)：$-2 - 1 = -3$，不能被 4 整除。
• 第 5 天 ($i=5$, 奇数)：$-3 + 2 = -1$，不能被 4 整除。
• 第 6 天 ($i=6$, 偶数)：$-1 - 1 = -2$，不能被 4 整除。最终结果为 -2。

样例 2： 输入：15 5 输出：14

算法提示

由于 $N$ 的范围高达 $10^{15}$，直接使用循环模拟（$O(N)$）会导致超时（仅限 50% 的分数）。

1. 规律观察：由于涉及“被 4 整除”和“正负反转”，数值的变化通常会进入一个较短的循环周期。
2. 寻找周期：记录每次操作后的 $(x \pmod 4, i \pmod 2)$ 状态。一旦状态重复，即可计算周期的步数和余额增量，从而利用取模运算直接跳过中间的大量循环。
3. 数据类型：请务必使用 long long 来处理 $N$ 和 $x$。

版权信息

• 项目： Macedonian Programming Contests 2026
• 赛事： Community and Regional competition
• 版权方： ZIM (北马其顿计算机科学家协会)