分解质因数问题（数论）

质因数问题（数论）"/>

分解质因数问题（数论）

就从我遇到的分解质因数问题开始说吧。

D - Power Products CodeForces - 1247D

传送门
这道题的题目意思贼好理解，就是给n个数，要求输出这个序列中任选两个数相乘满足x的k次幂的组合有多少种。(x为任意一个正整数，k为输入的指数）。

比赛的时候看了看，暴力肯定不行的1e5的范围，肯定T。这也算正式的接触数论里面的分解质因数吧。

我们都知道任意一个大于一的数都可以分解为质因数的乘积（口胡），所以一个数就可以分解为若干个最小质因数。通过分析这道题，要想达到k次幂，那这两个相乘的数，必定存在这样一个规则：

每个数的共同最小质因数的个数的和为k的倍数！

这个是很关键的，这就好办了，依次输入每个数，把这个数分解为最小质因数，和这个质因数对应所需满足k的倍数的次幂的个数保存起来，遇到可配对的情况，就加1，这个用map解决

#include <iostream>
#include <cstdio>
#include<cstdlib>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include<time.h>
#include <stack>
#include <list>
#include <set>
#include <sstream>
#include <iterator>
using namespace std;
#define FOPI freopen("input.in", "r", stdin)
#define DOPI freopen("output.out", "w", stdout)
#define ll long long int
#define fro(i,a,n) for(ll i=a;i<n;i++)
#define pre(i,a,n) for(ll i=n-1;i>=a;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define ls l,mid,rt<<1
#define rs mid+1,r,rt<<1|1
#define fi first
#define se second
#define s_d(a) scanf("%d",&a)
#define s_lld(a) scanf("%lld",&a)
#define s_s(a) scanf("%s",a)
#define s_ch(a) scanf("%c",&a)
typedef pair<ll,ll> P;
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
const double PI = 3.1415926535897932;
const double EPS=1e-6;
const int INF=0x3f3f3f3f;
const int maxn = 2e5+100;
int lowbit(int x){return x&(-x);}
map<vector<P>,ll> mp;//第一个存取每个数中质因数以及需要配对个数，
int main()//第二个存取，出现次数
{ios::sync_with_stdio(0);int n,k;cin>>n>>k;ll ans=0;fro(i,0,n){int temp;cin>>temp;vector<P> s;s.clear();int a=sqrt(temp);s.push_back(make_pair(1,1));//去除1的影响for(int i=2;i<=a;i++)//分解质因数{int num=0;while(temp%i==0){temp/=i;num++;}num%=k;if(num){s.push_back(make_pair(i,num));}}if(temp!=1)//3，5单独处理s.push_back(make_pair(temp,1));ans+=mp[s];fro(i,1,s.size()){s[i].se=k-s[i].se;}mp[s]++;}cout<<ans<<endl;return 0;
}