Day 12
题目描述
西西艾弗岛上共有 \(n\) 个仓库，依次编号为 \(1∼n\)。
每个仓库均有一个 \(m\) 维向量的位置编码，用来表示仓库间的物流运转关系。
具体来说，每个仓库 \(i\) 均可能有一个上级仓库 \(j\)，满足：仓库 \(j\) 位置编码的每一维均大于仓库 \(i\) 位置编码的对应元素。
比如编码为 \((1,1,1)\) 的仓库可以成为 \((0,0,0)\) 的上级，但不能成为 \((0,1,0)\) 的上级。
如果有多个仓库均满足该要求，则选取其中编号最小的仓库作为仓库 \(i\) 的上级仓库；如果没有仓库满足条件，则说明仓库 \(i\) 是一个物流中心，没有上级仓库。
现给定 \(n\) 个仓库的位置编码，试计算每个仓库的上级仓库编号。
输入格式
输入共 \(n+1\) 行。
输入的第一行包含两个正整数 \(n\) 和 \(m\)，分别表示仓库个数和位置编码的维数。
接下来 \(n\) 行依次输入 \(n\) 个仓库的位置编码。其中第 \(i\) 行\(（1≤i≤n）\)包含$ m$ 个整数，表示仓库 \(i\) 的位置编码。
输出格式
输出共 \(n\) 行。
第 \(i\) 行\(（1≤i≤n）\)输出一个整数，表示仓库 \(i\) 的上级仓库编号；如果仓库 \(i\) 没有上级，则第 \(i\) 行输出 \(0\)。
数据范围
\(50\%\) 的测试数据满足 \(m=2\)；
全部的测试数据满足 \(0<m≤10、0<n≤1000\)，且位置编码中的所有元素均为绝对值不大于 \(10^6\) 的整数。
输入样例：
4 2
0 0
-1 -1
1 2
0 -1
输出样例：
3
1
0
3
样例解释
对于仓库 \(2\)：\((−1,−1)\) 来说，仓库 \(1\)：\((0,0)\) 和仓库 \(3\)：\((1,2)\) 均满足上级仓库的编码要求，因此选择编号较小的仓库 \(1\) 作为其上级。
题目分析
语法题
数据量很小，按照题干描述暴力求每个点的上级编号即可，时间复杂度\(O(mn^2)\)
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n , m;
vector<int> p[N];
int f[N];
int main()
{
cin >> n >> m;
for(int i = 0 ; i < n ; i ++)
{
for(int j = 0 ; j < m ; j ++)
{
int x;
cin >> x;
p[i].push_back(x);
}
}
for(int i = 0 ; i < n ; i ++)
{
for(int j = 0 ; j < n ; j ++)
{
bool flag = true;
for(int k = 0 ; k < m ; k ++)
flag &= (p[i][k] < p[j][k]);
if(flag)
{
f[i] = j + 1;
break;
}
}
}
for(int i = 0 ; i < n ; i ++)
cout << f[i] << '\n';
return 0;
}
题目描述
质数（又称“素数”）是指在大于 \(1\) 的自然数中，除了 \(1\) 和它本身以外不再有其他因数的自然数。
小 \(P\) 同学在学习了素数的概念后得知，任意的正整数 \(n\) 都可以唯一地表示为若干素因子相乘的形式。
如果正整数 \(n\) 有 \(m\) 个不同的素数因子 \(p_1,p_2,…,p_m\)，则可以表示为：\(n=p_1^{t_1}×p_2^{t_2}×…×p_m^{t_m}\)。
小 \(P\) 认为，每个素因子对应的指数 \(t_i\) 反映了该素因子对于 \(n\) 的重要程度。
现设定一个阈值 \(k\)，如果某个素因子 \(p_i\) 对应的指数 \(t_i\) 小于 \(k\)，则认为该素因子不重要，可以将\(p_i^{t_i}\) 项从 \(n\) 中除去；反之则将 \(p_i^{t_i}\) 项保留。
最终剩余项的乘积就是$ n$ 简化后的值，如果没有剩余项则认为简化后的值等于 \(1\)。
试编写程序处理 \(q\) 个查询：
每个查询包含两个正整数 \(n\) 和 \(k\)，要求计算按上述方法将 \(n\) 简化后的值。
输入格式
输入共 \(q+1\) 行。
输入第一行包含一个正整数 \(q\)，表示查询的个数。
接下来 \(q\) 行每行包含两个正整数 \(n\) 和 \(k\)，表示一个查询。
输出格式
输出共 \(q\) 行。
每行输出一个正整数，表示对应查询的结果。
数据范围
\(40\%\) 的测试数据满足：\(n≤1000\)；
\(80\%\) 的测试数据满足：\(n≤10^5\)；
全部的测试数据满足：\(1<n≤10^{10}\) 且 \(1<k,q≤10\)。
输入样例：
3
2155895064 3
2 2
10000000000 10
输出样例：
2238728
1
10000000000
样例解释
查询一：
- \(n=2^3×3^2×23^4×107\)
- 其中素因子\(3\) 指数为 \(2\)，\(107\) 指数为 \(1\)。将这两项从 \(n\) 中除去后，剩余项的乘积为 \(2^3×23^4=2238728\)。
查询二：
- 所有项均被除去，输出 \(1\)。
查询三：
- 所有项均保留，将 \(n\) 原样输出。
题目分析
质因子分解，记录下每次的质因子和对应幂，再去检查一边，小于\(k\)的从结果中除去即可
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
typedef long long LL;
LL n;
int k;
map<LL , int> prime;
void solve()
{
LL res = n;
prime.clear();
for(int i = 2 ; i <= n / i ; i ++)
{
while(n % i == 0)
{
n /= i;
prime[i] ++;
}
}
if(n > 1) prime[n] ++;
for(auto it : prime)
{
LL p = it.first;
int t = it.second;
if(t < k)
for(int i = 0 ; i < t ; i ++)
res /= p;
}
cout << res << '\n';
}
int main()
{
int T;
cin >> T;
while(T --)
{
cin >> n >> k;
solve();
}
return 0;
}#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
typedef long long LL;
LL n;
int k;
map<LL , int> prime;
void solve()
{
LL res = n;
prime.clear();
for(int i = 2 ; i <= n / i ; i ++)
{
while(n % i == 0)
{
n /= i;
prime[i] ++;
}
}
if(n > 1) prime[n] ++;
for(auto it : prime)
{
LL p = it.first;
int t = it.second;
if(t < k)
for(int i = 0 ; i < t ; i ++)
res /= p;
}
cout << res << '\n';
}
int main()
{
int T;
cin >> T;
while(T --)
{
cin >> n >> k;
solve();
}
return 0;
}