首页 > 试题广场 >

异次元空间

[编程题]异次元空间

热度指数：249 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有n个异次元空间，第0天的晚上第i个异次元空间有 $a_i$ 个暗黑物质。

每天早上，第i个异次元空间会增加 $d_i$ 个暗黑物质。

每天中午，如果某异次元空间的暗黑物质数量大于等于 ${P}$ (保证 ${P}$ 为质数),则该异次元空间会有 ${P}$ 个暗黑物质产生反应而消失，直到剩余的暗黑物质少于 ${P}$ 个。

每天晚上，对于每个异次元空间，牛牛都可以选择是否冻结/解冻该空间。当异次元空间被冻结时，这个异次元空间无法继续产生暗黑物质。（第0天晚上也可以进行冻结操作）

现在牛牛想知道，最少可以在第几天的晚上有不少于m个异次元空间有刚好k个暗黑物质。

示例1

输入

3,2,5,[1,0,3],[2,2,1],2

输出

说明

第0天晚上牛牛冻结第二个空间
第一天晚上各个空间物质数量为[3,0,4]，牛牛不进行操作
第二天晚上各个空间物质数量为[0,0,4]，此时牛牛为第二个空间解冻
第三个晚上各个空间物质数量为[2,2,1]，此时已经有两个空间有刚好2个物质，满足条件

备注:



第一个参数n代表异次元空间数目
第二个参数为整数m，含义见题面
第三个参数为整数P，含义见题面
第四个参数vector a包含n个元素代表每个异次元空间一开始的暗黑物质数目
第五个参数vector b包含m个元素代表每个异次元空间每天增加的暗黑物质数目
第六个参数为整数k，含义见题面

算法知识视频讲解

练习写bug

发表于 2020-07-19 10:12:14

对于每个空间需要的天数满足公式 (初始值 + 天数 * 每天增长量) % p = k ，即上面的式子等价于：等式的两端同乘以 d[i] 的逆元：问题就变成了如何求 d[i] 的逆元，我们令 x 表示 d[i] 的逆元：因为 p 为质数，所以保证了 gcd(d[i], p) = 1 ，由扩展欧展开全文

未来0116

发表于 2021-08-17 23:09:53

一.题目描述NC567异次元空间数组a表示n个异次元空间的暗物质数量，每天每个异次元空间的暗物质数量会增加d数组中对应元素的值，可以选择冻结空间使之每天不再增加，也可以选择解除冻结，如果异次元空间的暗物质数量大于等于P，会对P取余，P一定为质数，最少可以在第几天的晚上有不少于m个异次元空间有刚好k个展开全文

球球了给孩子一个offer吧

发表于 2021-10-06 17:00:13

题目：有n个异次元空间，第0天的晚上第i个异次元空间有a[i]个暗黑物质。每天可以增长d[i],当增长到了P时，会有P个暗黑物质产生反应而消失，直到剩余的暗黑物质少于P个。还可以选择让某个异空间停止增长或者继续增长。求最少多少天可以使得有至少m个异次元空间达到k 方法一：拓展欧几里得算法求逆元展开全文