2020/4/21
1.质因数分解 数学题 【算法|2020/4/21每日一练】传送门
题意就是给出一个长度为n<=1e5的序列和一个k范围[2,100]，元素范围[1,1e5]。求aiaj=pow(x,k) ，x是任意的。
很容易想到用除过去map找，于是我就先预处理出每个数需要的最小数num，比如k=3时，2所需要的num就是4，因为24=8，num[12]是18因为12*18==pow(6,3)。这里我是用质因数分解和快速幂做的。然后x就会是num[aj]*pow(枚举的数,k)，因为是次幂所以枚举不会很多，在logn的范围。
复杂度在nloglog左右？
跑了1.7s，还是挺悬的
搜了下其他人的解法，不用用到快速幂，质因数分解也很快。
大概就是质因数次方k模一下k，然后map.find（k-次方）
跑了一下只用了90+ms
别人家的解法
#include
using namespace std;
typedef long long ll;
typedef pair pii;
typedef pair pll;
const int maxn = 1e5 + 5;
const ll inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
#define all(x) x.begin(), x.end()
int prime[maxn], vis[maxn];
ll num[maxn];
int n, k;
ll ksm(ll a, ll n) {
ll ans = 1;
while (n) {
if (n & 1) {
if (log10(a) + log10(ans) > 10) return -1;
ans = ans * a;
}
if (log10(a) > 5) return -1;
a = a * a;
n >>= 1;
}
return ans;
}
void init() {
num[1] = 1;
for (int i = 2;
i < maxn;
i++) {
num[i] = 1;
if (!vis[i]) prime[++prime[0]] = i;
for (int j = 1;
j <= prime[0] && i * prime[j] < maxn;
j++) {
vis[i * prime[j]] = true;
if (i % prime[j] == 0) break;
}
}
for (int i = 2;
i < maxn;
++i) {
int now = i;
for (int j = 1;
j <= prime[0] && now >= prime[j];
++j) {
int cnt = 0;
while (now % prime[j] == 0) {
now /= prime[j];
cnt++;
}
num[i] *= ksm(prime[j], (cnt + k - 1) / k * k - cnt);
if (num[i] < 0) {
num[i] = -1;
break;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k;
init();
vector a(n);
for (int i = 0;
i < n;
++i) {
cin >> a[i];
}
map mp;
ll ans = 0;
for (int i = 0;
i < n;
++i) {
if (num[a[i]] == -1) continue;
for (int j = 1;
;
++j) {
ll temp = ksm(j, k);
if (temp == -1 || log10(temp) + log10(num[a[i]]) > 5) {
break;
}
if (mp.count(temp * num[a[i]])) ans += mp[temp * num[a[i]]];
}
mp[a[i]]++;
}
cout << ans << endl;
return 0;
}
推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）
- 网络|简单聊聊压缩网络