分解质因数

https://en.wikipedia.org/wiki/Integer_factorization

直接暴力

最简单的分解质因数
$O(\sqrt n)$ 分解质因数

int p[20];
int a[20];
int k;
for (int i = 2; i * i <= n; i++)
{
	if (n % i == 0)
	{
		p[k] = i;
		while (n % i == 0)
		{
			a[k]++;
			n /= i;
		}
		k++;
	}
}
if (n > 1)
{
	p[k] = n;
	a[k] = 1;
	k++;
}

唯一分解定理

Pollard's rho algorithm

时间复杂度是 O(n**(1/4))
https://www.luogu.com.cn/problem/P4718
https://oi-wiki.org/math/number-theory/pollard-rho/

参考题目

CF1225D Power Products

https://codeforces.com/problemset/problem/1225/D
https://www.luogu.com.cn/problem/CF1225D

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100001;
typedef long long ll;
int n, m, x;
ll y, z, ans, s[N];
void gao(int p, int k)
{
	for (int i = 0; i < k; i++)
	{
		y *= p;
	}
	for (int i = 0; i < (m - k) % m; i++)
	{
		z *= p;
		if (z > 100000)
		{
			z = 0;
		}
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> x;
		y = z = 1;
		for (int i = 2; i * i <= x; i++)
		{
			if (x % i == 0)
			{
				int c = 0;
				while (x % i == 0)
				{
					c++;
					x /= i;
				}
				gao(i, c % m);
			}
		}
		if (x > 1)
		{
			gao(x, 1);
		}
		ans += s[z];
		s[y]++;
	}
	cout << ans << endl;
	return 0;
}

题解

CF1228C Primes and Multiplication

https://codeforces.com/problemset/problem/1228/C
https://www.luogu.com.cn/problem/CF1228C

参考代码

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
typedef long long ll;
int x;
ll n, z = 1;
ll pw(ll x, ll y)
{
	ll re = 1;
	for (; y > 0; y >>= 1)
	{
		if (y & 1)
		{
			re = re * x % mod;
		}
		x = x * x % mod;
	}
	return re;
}
ll gao(ll n, int p)
{
	ll re = 0;
	while (n > 0)
	{
		n /= p;
		re += n;
	}
	return re;
}
int main()
{
	cin >> x >> n;
	for (int i = 2; i * i <= x; i++)
	{
		if (x % i == 0)
		{
			while (x % i == 0)
			{
				x /= i;
			}
			z = z * pw(i, gao(n, i)) % mod;
		}
	}
	if (x > 1)
	{
		z = z * pw(x, gao(n, x)) % mod;
	}
	printf("%lld\n", z);
	return 0;
}