[CodeForces - 1225D]Power Products 【数论】 【分解质因数】
标签：题解 codeforces题解 数论
题目描述
Time limit
2000 ms
Memory limit
524288 kB
Source
Technocup 2020 - Elimination Round 2
Tags
hashing math number theory *1900
Site
https://codeforces.com/problemset/problem/1225/D
题面
Example
Input
6 3
1 3 9 8 24 1
Output
5
题目大意
给定(n, k)，序列(a[1 cdots n])。问在该序列中能找到多少组序偶(<i, j>)满足(a_i cdot a_j = x ^ k)（其中(x)可以为任意整数）。
例如，
(n = 6, k = 3, a[1 cdots n] = [1, 3, 9, 8, 24, 1])。
则有$$a_1 cdot a_4 = 1 cdot 8 = 8 = 2 ^ 3 a_1 cdot a_6 = 1 cdot 1 = 1 = 1 ^ 3 a_2 cdot a_3 = 3 cdot 9 = 27 = 3 ^ 3 a_3 cdot a_5 = 9 cdot 24 = 216 = 6 ^ 3 a_4 cdot a_6 = 8 cdot 1 = 8 = 2 ^ 3 $$
共五组情况，所以输出5。
解析
这道题是一道比较裸的数论题，很容易让人直接想到质因数分解。虽然我没有想到，当时打比赛都没有做到D题。
-
这题首先不考虑数论的知识，把这种求序偶个数的问题抽象出来。
把这道题抽象为给定(n, k)，序列(a[1 cdots n])。问在该序列中能找到多少组序偶(<i, j>)满足(a_i + a_j = k)。
这个问题其实很好解决，只要稍微想一下就可以得出答案。令(cnt[i][j])为到第(i)个位置，数字(j)在之前出现的次数。那么答案应该是(sum_i^ncnt[i][k - a[i]])。
在实际编程过程中，因为我们每到一个数(a[i])， (cnt[i][a[i]])实际上是在上一个(cnt[i - 1][a[i]])基础上得来的，而这个(cnt[i - 1][a[i]])之后就再也没有用了，其他的(cnt[i - 1][1 cdots INF])也没有改变，所以我们可以将这个(cnt)数组降到一维，这个思想也叫作滚动数组。 -
下面回到这个问题，把关键的(a_i cdot a_j = x ^ k)加入其中。
首先我们要知道当给定了(k)，即使(x)的值是不确定的，对于(t cdot s = x ^ k)，对于每一个(t)都只有唯一的(s)与之对应。
对(t)质因数分解，得
则$$s = p_1^{k - (alpha_1 % k)} cdot p_2^{k - (alpha_2 % k)} cdot p_3^{k - (alpha_3 % k)} cdot dots$$
所以对于每个(t)我们只要看之前有多少个这样的(s)出现就可以了。
而对于每个(a_i(t))我们实际上要记录的是它的(t_0)形式，因为只有这种形式才对答案有贡献。
- 这样我们在对每个(a_i)进行质因数分解的时候就顺带把(s)的值也求出来，最后(sum_i^ncnt[x ^ k div a[i]])即为答案（(cnt)为滚动数组，即到当前(i)位置，之前的数字(x ^ k div a[i])出现的个数）。
通过代码
/*
Status
Accepted
Time
46ms
Memory
396kB
Length
1076
Lang
GNU G++11 5.1.0
Submitted
2019-12-20 16:42:32
RemoteRunId
67272043
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 50;
int cnt[MAXN];
int x, n, k;
ll y; //注意y要开long long.
inline int read() //快读，1e5数据输入量.
{
int res = 0;
char ch;
ch = getchar();
while(!isdigit(ch))
ch = getchar();
while(isdigit(ch)){
res = (res << 3) + (res << 1) + ch - 48;
ch = getchar();
}
return res;
}
void work(int p, int &t)
{
int c = 0;
while(t % p == 0)
t /= p, c ++;
c %= k;
for(int i = 0; i < c; i ++)
x *= p;
for(int i = 0; i < (k - c) % k; i ++){ //(k - c) % k是针对c为0的情况的特判.
y *= p;
if(y >= MAXN){
y = MAXN;
break;
}
}
return;
}
int main()
{
ll ans = 0;
n = read(), k = read();
for(int i = 1; i <= n; i ++){
int t;
t = read();
x = y = 1; //x对应的是t0，y对应的是s.
for(int j = 2; j * j <= t; j ++) //质因数分解.
if(t % j == 0) work(j, t);
if(t > 1) work(t, t);
if(y < MAXN){ //如果得到的y超过1e5，就超过范围找不到了，就没有意义.
ans += cnt[y];
cnt[x] ++;
}
}
printf("%I64d", ans);
return 0;
}