カーマイケル関数
(math/carmichael_function.hpp)

#pragma once
#include<map>
/**
 * @brief カーマイケル関数
 */
template<typename T>
auto carmichael_function(T n){
    map<T,long long>ret;
    for(auto i=2;i*i<=n;i++){
        while(n%i==0){
            ret[i]++;
            n/=i;
        }
    }
    if(n!=1)ret[n]=1;
    long long res=1;
    for(auto d:ret){
        if(d.first==2){
            if(d.second<3)res=pow(d.first,d.second-1);
            else res=pow(d.first,d.second-2);
        }
        else res=lcm(res,(long long)pow(d.first,d.second-1)*(d.first-1));
    }
    return res;
}

#line 2 "math/carmichael_function.hpp"
#include<map>
/**
 * @brief カーマイケル関数
 */
template<typename T>
auto carmichael_function(T n){
    map<T,long long>ret;
    for(auto i=2;i*i<=n;i++){
        while(n%i==0){
            ret[i]++;
            n/=i;
        }
    }
    if(n!=1)ret[n]=1;
    long long res=1;
    for(auto d:ret){
        if(d.first==2){
            if(d.second<3)res=pow(d.first,d.second-1);
            else res=pow(d.first,d.second-2);
        }
        else res=lcm(res,(long long)pow(d.first,d.second-1)*(d.first-1));
    }
    return res;
}