传送门 当然是考虑 $n$ 的每个质数 $p$ 对答案的贡献 考虑 $p^k$ 在 $[1,m]$ 中出现了几次，显然是 $\left \lfloor \frac{m}{p^k} \right \rfloor$ 次 那么对于 $p^k$ ，它目前的贡献就是 $p^{\left \lfloor \
传送门
当然是考虑 $n$ 的每个质数 $p$ 对答案的贡献
考虑 $p^k$ 在 $[1,m]$ 中出现了几次，显然是 $\left \lfloor \frac{m}{p^k} \right \rfloor$ 次
那么对于 $p^k$ ，它目前的贡献就是 $p^{\left \lfloor \frac{m}{p^k} \right \rfloor}$ ，注意这里不是 $p^{k\left \lfloor \frac{m}{p^k} \right \rfloor}$，因为之后计算对于 $k‘<k,p^{k‘}$ 时的贡献会算到
然后现在问题是求 $n$ 的质因数，显然 $n$ 最多只有一个质因数大于 $\sqrt{n}$ ，那么我们只要筛 $\sqrt{n}$ 以内的质数即可
注意可能乘的时候可能爆 $long\ long$
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<map> #include<vector> using namespace std; typedef long long ull; inline ull read() { ull x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e6+7,mo=1e9+7; ull n,m,ans=1,pri[N],tot; vector <ull> V; bool not_pri[N]; inline ull ksm(ull x,ull y) { ull res=1; while(y) { if(y&1) res=res*x%mo; x=x*x%mo; y>>=1; } return res; } int main() { n=read(),m=read(); int t=sqrt(n)+1; for(int i=2;i<=t;i++) { if(!not_pri[i]) pri[++tot]=i; for(int j=1;j<=t;j++) { ull g=i*pri[j]; if(g>t) break; not_pri[g]=1; if(!(i%pri[j])) break; } } for(int i=1;i<=tot;i++) if(!(n%pri[i])) { V.push_back(pri[i]); while(!(n%pri[i])) n/=pri[i]; } if(n>1) V.push_back(n); int len=V.size(); for(int i=0;i<len;i++) { for(ull now=V[i];now<=m;now*=V[i]) { ans=ans*ksm(V[i],m/now)%mo; if(m/V[i]<now) break;//防止爆 unsigned long long } } cout<<ans<<endl; return 0; }