#include "math/prime_factor.hpp"
#pragma once #include<vector> #include<numeric> #include<cmath> #include<algorithm> #include<map> #include"is_prime.hpp" /** * @brief 素因数分解(高速) */ void __prime_factor(long long n,long long& c,std::vector<long long>& v){ if(n==1)return; if(n%2==0){ v.emplace_back(2); __prime_factor(n/2,c,v); return; } if(is_prime(n)){ v.emplace_back(n); return; } while(1){ long long x=2,y=2,d=1; while(d==1){ x=((__int128_t)x*x+c)%n; y=((__int128_t)y*y%n+c)%n; y=((__int128_t)y*y%n+c)%n; d=std::gcd(std::abs(x-y),n); } if(d==n){ c++; continue; } __prime_factor(d,c,v); __prime_factor(n/d,c,v); return; } } std::map<long long,long long> prime_factor(long long n){ std::vector<long long>v; long long c=1; __prime_factor(n,c,v); std::map<long long,long long>m; for(auto e:v){ m[e]++; } return m; }
#line 2 "math/prime_factor.hpp" #include<vector> #include<numeric> #include<cmath> #include<algorithm> #include<map> #line 2 "math/is_prime.hpp" #include <initializer_list> /** * @brief 素数判定(高速) */ bool is_prime(long long n){ if(n<=1)return 0; if(n==2)return 1; if(n%2==0)return 0; long long s=0,d=n-1; while(d%2)d/=2,s++; auto mod_pow=[](__int128_t a,__int128_t b,__int128_t n){ long long res=1; while(b){ if(b%2)res=res*a%n; a=a*a%n; b/=2; } return (long long)(res); }; for(long long e:{2,3,5,7,11,13,17,19,23,29,31,37}){ if(n<=e)break; if(mod_pow(e,d,n)==1)continue; bool b=1; for(int i=0;i<s;i++){ if(mod_pow(e,d<<i,n)==n-1)b=0; } if(b)return 0; } return 1; } #line 8 "math/prime_factor.hpp" /** * @brief 素因数分解(高速) */ void __prime_factor(long long n,long long& c,std::vector<long long>& v){ if(n==1)return; if(n%2==0){ v.emplace_back(2); __prime_factor(n/2,c,v); return; } if(is_prime(n)){ v.emplace_back(n); return; } while(1){ long long x=2,y=2,d=1; while(d==1){ x=((__int128_t)x*x+c)%n; y=((__int128_t)y*y%n+c)%n; y=((__int128_t)y*y%n+c)%n; d=std::gcd(std::abs(x-y),n); } if(d==n){ c++; continue; } __prime_factor(d,c,v); __prime_factor(n/d,c,v); return; } } std::map<long long,long long> prime_factor(long long n){ std::vector<long long>v; long long c=1; __prime_factor(n,c,v); std::map<long long,long long>m; for(auto e:v){ m[e]++; } return m; }