解题思路
矩阵中每个元素为:
Ci,j=ai⋅bj
需要统计满足:
Ci,j≥k
P4840.第2题-矩阵计数
题目内容
给定两个整数序列 a(长度为 n)与 b(长度为m)。
构造一个 n×m的矩阵C,其中Ci,j=ai⋅bj。
给定阈值k,请你统计矩阵中有多少个元素满足 Ci,j≥k。
输入描述
每个测试文件均包含多组测试数据。
保证所有测试中n+m 的总和不超过 2×105。
输出描述
对每组数据输出一行,一个整数,表示满足 ai⋅bj≥k 的矩阵元素个数
样例1
输入
3
3 3 6
1 2 3
2 3 4
2 4 1
0 5
0 0 1 10
2 3 1
1 1
1 1 1
输出
5
2
6
说明
1⋅22⋅23⋅21⋅32⋅33⋅31⋅42⋅43⋅4=2463694812
其中 ≥6的元素共有 5 个。
- 第二组:仅 (1,5) 与 (10,5)的乘积 ≥1,答案为 2。
- 第三组:所有条目均为 1,共有 2×3=6 个满足 k=1