Kyopro Library
 
読み取り中…
検索中…
一致する文字列を見つけられません
prime_factorize.hpp
[詳解]
1#pragma once
2#include"../../kyopro_library/template.hpp"
3#include"../../kyopro_library/math/primality_test.hpp"
4
5/// @brief ポラードのロー法で n を素因数分解する
6/// @note O(N^(1/4))
7/// @ref https://qiita.com/t_fuki/items/7cd50de54d3c5d063b4a
8/// @ref verify: https://algo-method.com/tasks/553
10 if(PrimalityTest(n)) return {{n,1}};
11 auto find_factor=[](auto&& find_factor, ll n)-> ll {
12 lll m=(ll)pow(n,0.125)+1;
13 auto _gcd=[](lll a, lll b) {
14 while(a) b%=a,swap(a,b);
15 return b;
16 };
17 auto _abs=[](lll x) { return x<0?-x:x; };
18 for(ll c=1; c<=n; c++) {
19 auto f=[&](lll x) { return((x%n)*(x%n)+c)%n; };
20 lll y=0,r=1,q=1,g=1,k=0,x=0,ys=0;
21 while(g==1) {
22 x=y;
23 while(k<r*3/4) y=f(y),k++;
24 while(k<r&&g==1) {
25 ys=y;
26 for(int i=0; i<min(m,r-k); i++) y=f(y), q=q*_abs(x-y)%n;
27 g=_gcd(q,n); k+=m;
28 }
29 k=r; r*=2;
30 }
31 if(g==n) {
32 g=1,y=ys;
33 while(g==1) y=f(y), g=_gcd(_abs(x-y),n);
34 }
35 if(g<n) {
36 if(PrimalityTest(g)) return g;
37 if(PrimalityTest(n/g)) return n/g;
38 return find_factor(find_factor,g);
39 }
40 }
41 return 0;
42 };
43 map<ll,ll> mp;
44 ll i=2;
45 while(i*i<=n) {
46 ll k=0;
47 while(n%i==0) n/=i, k++;
48 if(k) mp[i]=k;
49 i+=i%2+1;
50 if(i==101 && n>=(1ll<<20)) {
51 while(n>1) {
52 if(PrimalityTest(n)) mp[n]=1, n=1;
53 else {
54 ll j=find_factor(find_factor,n);
55 k=0;
56 while(n%j==0) n/=j,k++;
57 mp[j]=k;
58 }
59 }
60 }
61 }
62 if(n>1) mp[n]=1;
63 vector<pair<ll,ll>> ret;
64 for(auto p: mp) ret.push_back(p);
65 sort(ret.begin(),ret.end());
66 return ret;
67}
bool PrimalityTest(ll n)
ミラーラビン素数判定法により n が素数であるかを判定する
vector< pair< ll, ll > > PrimeFactorize(ll n)
ポラードのロー法で n を素因数分解する