[蓝桥杯]春晚魔术【算法赛】

目录

输入格式

输出格式

样例输入

样例输出

运行限制

解决思路

代码说明

复杂度分析

问题描述

在蓝桥卫视春晚的直播现场，魔术师小蓝表演了一个红包魔术。只见他拿出了三个红包，里边分别装有 A、B 和 C 个金币。而后，他挥动魔术棒，念动咒语“福禄寿喜财神到～”，对红包里的金币进行 NN 次变换。每次变换，每个红包的金币数量都会变成其他两个红包金币数量的乘积。

例如：

• 初始金币数量 A=2A=2，B=3B=3，C=5C=5，进行 N=1N=1 次变换后，金币数量变为 1515，1010，66。
• 初始金币数量 A=1A=1，B=2B=2，C=3C=3，进行 N=2N=2 次变换后，金币数量变为 66，1212，1818。

变换结束后，小蓝得意地问观众：“现在，你们知道三个红包里金币的总乘积是多少吗？” 他飞快地心算了一下，并报出一个数字：“让我来揭晓答案吧！总乘积是…嗯…（不知道算没算对，只知道算得快）”。

作为观众，请你计算 NN 次变换后，三个红包金币数量的总乘积。由于结果可能很大，请输出其对 109+7109+7 取模的结果。

输入格式

第一行包含一个整数 TT (1≤T≤103)(1≤T≤103)，表示测试用例的数量。

接下来的 TT 行，每行包含四个整数 AA，BB，CC 和 NN（1≤A,B,C,N≤1091≤A,B,C,N≤109），表示一组数据。

输出格式

对于每组数据，输出一个整数，表示 NN 次变换后三个红包金币数量的总乘积。由于结果可能很大，请输出其对 109+7109+7 取模的结果。

样例输入

2
2 3 5 1
1 2 3 2

样例输出

900
1296

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Java	2s	256M
Python3	3s	256M
PyPy3	3s	256M
Go	3s	256M
JavaScript	3s	256M

总通过次数: 342  |  总提交次数: 774  |  通过率: 44.2%

难度: 中等   标签: 欧拉降幂, 快速幂, 思维, 数学

解决思路

1. 问题分析：每次变换，红包金币数量变为其他两个红包金币数量的乘积。经过数学推导，N次变换后的总乘积为 (𝐴×𝐵×𝐶)2𝑁mod  (109+7)(A×B×C)2Nmod(109+7)。

2. 关键观察：

   • 初始总乘积 𝑆0=𝐴×𝐵×𝐶S0​=A×B×C。

   • 经过N次变换后，总乘积 𝑆𝑁=𝑆02𝑁SN​=S02N​。

3. 处理大数：

   • 使用模 𝑀=109+7M=109+7（质数），其欧拉函数 𝜙(𝑀)=𝑀−1=109+6ϕ(M)=M−1=109+6。

   • 若 𝐴×𝐵×𝐶≡0mod  𝑀A×B×C≡0modM，则结果直接为0（因为后续幂运算仍为0）。

   • 否则，计算指数 2𝑁mod  𝜙(𝑀)2Nmodϕ(M)，再计算 𝑆0S0​ 的该指数次幂模 𝑀M。

4. 高效计算：

   • 使用快速幂算法计算模幂，时间复杂度 𝑂(log⁡𝑁)O(logN) 和 𝑂(log⁡exponent)O(logexponent)。

   • 使用 __int128 处理大数乘法中的溢出问题（适用于支持该类型的编译器）。

#include <iostream>
#include <cstdio>
using namespace std;const long long MOD = 1000000007;
const long long PHI = 1000000006;  // MOD-1// 快速幂函数：计算 (base^exp) % mod
long long fast_pow(long long base, long long exp, long long mod) {if (exp == 0) {return 1 % mod;  // 任何数的0次幂为1（模mod）}base %= mod;long long result = 1;while (exp > 0) {if (exp & 1) {result = (result * base) % mod;}base = (base * base) % mod;exp >>= 1;}return result;
}int main() {int T;scanf("%d", &T);while (T--) {long long A, B, C, N;scanf("%lld %lld %lld %lld", &A, &B, &C, &N);// 计算 base = (A * B * C) % MOD，使用 __int128 避免溢出long long a_mod = A % MOD;long long b_mod = B % MOD;long long c_mod = C % MOD;__int128 temp = static_cast<__int128>(a_mod) * b_mod;temp %= MOD;temp = temp * c_mod;temp %= MOD;long long base = static_cast<long long>(temp);// 若 base 为 0，则结果为 0if (base == 0) {printf("0\n");continue;}// 计算指数：exponent = 2^N mod PHIlong long exponent = fast_pow(2, N, PHI);// 计算结果：result = base^exponent mod MODlong long result = fast_pow(base, exponent, MOD);printf("%lld\n", result);}return 0;
}

代码说明

1. 常量定义：

   • MOD = 1000000007：取模基数。

   • PHI = 1000000006：欧拉函数值（MOD - 1）。

2. 快速幂函数 fast_pow：

   • 高效计算 baseexpmod  modbaseexpmodmod。

   • 使用二进制分解将时间复杂度降至 𝑂(log⁡exp)O(logexp)。

3. 主函数：

   • 读取测试用例数 𝑇T。

   • 对每个测试用例：

     • 读取 𝐴,𝐵,𝐶,𝑁A,B,C,N。

     • 计算初始乘积模 𝑀𝑂𝐷MOD（使用 __int128 避免中间结果溢出）。

     • 若初始乘积模 𝑀𝑂𝐷MOD 为 0，则输出 0。

     • 否则，计算指数 2𝑁mod  PHI2NmodPHI，再计算最终结果 baseexponentmod  MODbaseexponentmodMOD。

4. 输入输出：

   • 使用 scanf 和 printf 提高效率。

复杂度分析

• 时间复杂度：每个测试用例执行两次快速幂运算（一次计算指数，一次计算结果），每次 𝑂(log⁡exponent)O(logexponent)。总时间复杂度 𝑂(𝑇log⁡𝑁)O(TlogN)，满足 𝑇≤1000T≤1000 和 𝑁≤109N≤109 的限制。

• 空间复杂度：𝑂(1)O(1)，仅使用常数空间。