link:
https://ac.nowcoder.com/acm/contest/5961/B
description:
n个序列 每个序列有m个数 他们都是k的整数次幂 n个序列中所有数相乘乘积最大的值是多少 取模后输出
solution:
n和m范围不大 可以接受n * m 如果暴力计算的话 会因为取模操作而导致 大的数取模后变的比原来小的数更小 所以没法直接暴力
关键点在于他们都是k次幂 我们可以计算每个序列的指数之和 即 a[i][j] = k ^ pw 计算每个序列pw之和 取最大的 最后快速幂一下就可以得到答案了
如何快速得到指数pw 并且判断是否和a[i][j] 是本题关键 a[i][j] 范围在1e12 跑100次幂范围肯定没问题 使用pow函数计算
这样交了一发T了 复杂度还是不够优秀 毕竟pow函数有点玄学 把pow改成没有取模的快速幂 ac 算是卡了个常数 跑了900ms
最快的是对k的1到100次幂的数直接打表 然后1到100的范围暴力找 复杂度是 n * m * 100 跑了400ms
其次还有对n个序列中每个数a[i][j] /k 计算幂次 开个数组记录一下 这样跑了1200ms (可能是因为位数太多 也能ac
code
#include <bits/stdc++.h> using namespace std; #define LL long long LL mod; LL quickpow(LL a,LL b){ LL res = 1; while(b){ if(b & 1){ res = res * a % mod; } b >>= 1; a = a * a % mod; } return res; } LL pw[105]; int main() { int n,m; LL k; scanf("%d%d%lld%lld",&n,&m,&k,&mod); int ma = 0; pw[1] = k; for(int i = 2;i <= 100;i ++){ pw[i] = pw[i - 1] * k; } for(int i = 1;i <= n;i ++){ int sum = 0; for(int j = 1;j <= m;j ++){ LL x;scanf("%lld",&x); for(int l = 1;l <= 100;l ++){ if(pw[l] == x){ sum += l; break; } } } ma = max(ma,sum); } printf("%lld\n",quickpow(k,1LL * ma)); return 0; }