素因数分解(高速)
(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;
}