题意:
给你m个M点,n个N点,M都是质数,N是和它相连的M的乘积,然后告诉你每个N点的值,求M点
直接对每个N分解质因数即可,测试欧拉筛筛到4e7再试除法在学校的OJ最多可以91分
然后看了官方题解,第一种推荐的是Pollard-Rho算法
然后找了一些资料
下面是代码,摘自以上文章大佬们的代码
分解质因数
#include<iostream>
#include<random>
#include<cmath>
#include<unordered_map>
#include<set>
using namespace std;
typedef long long ll;
typedef __int128_t lll;
const int M=1e5+10;
set<ll>prime;
int n,m,k;
unordered_map<ll, ll> um;
ll factor[M],tot;
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
ll qpow(ll a, ll n, ll p)
{
ll ans=1;
while(n)
{
if(n&1)
ans=(__int128)ans*a%p;
a=(__int128)a*a%p;
n>>=1;
}
return ans;
}
bool Miller_Rabin(ll x)
{
if (x<3)
return x==2;
if (x%2==0)
return false;
ll A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}, d = x - 1, r = 0;
while (d%2==0)
d/=2,++r;
for (auto a : A)
{
ll v=qpow(a,d,x);
if(v<=1||v==x-1)
continue;
for(int i=0;i<r;++i)
{
v=(__int128)v*v%x;
if (v==x-1&&i!=r-1)
{
v=1;
break;
}
if (v==1)
return false;
}
if (v!=1)
return false;
}
return true;
}
ll Pollard_Rho(ll N)
{
if(N==4)
return 2;
if(Miller_Rabin(N))
return N;
random_device seed;
ranlux48 engine(seed());
uniform_int_distribution<> distrib(1, N-1);
while(1)
{
ll c=distrib(engine);
auto f=[=](ll x)
{
return ((lll)x*x+c)%N;
};
ll t=0,r=0,p=1,q;
do
{
for(int i=0;i<128;i++)
{
t=f(t),r=f(f(r));
if(t==r||(q=(lll)p*abs(t-r)%N)==0)
break;
p=q;
}
ll d=gcd(p,N);
if(d>1)return d;
}while(t!=r);
}
}
ll max_prime_factor(ll x)
{
if (um.count(x))
return um[x];
ll fac = Pollard_Rho(x);
if (fac == 1)
um[x] = x;
else
um[x] = max(max_prime_factor(fac), max_prime_factor(x / fac));
return um[x];
}
void findfac (ll n){
if (Miller_Rabin(n)) {
prime.insert(n);
return;
}
ll p = n;
while (p>=n)
p = Pollard_Rho(p);
findfac(p);
findfac(n/p);
}
signed main()
{
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
ll x;
scanf("%lld",&x);
if(um[x])continue;
findfac(x);
um[x]=1;
}
for(set<ll>::iterator p=prime.begin();p!=prime.end();p++) cout<<*p<<" ";
return 0;
}