[Luogu5106]dkw的lcm

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 4 typedef long long ll;
 5 using namespace std;
 6 
 7 const int N=1000010,mod=1e9+7;
 8 int n,k,tot,ans,b[N],p[N];
 9 
10 int ksm(int a,int b,int mod){
11     int res=1;
12     for (; b; a=1ll*a*a%mod,b>>=1)
13         if (b & 1) res=1ll*res*a%mod;
14     return res;
15 }
16 
17 void init(){
18     rep(i,2,n){
19         if (!b[i]) p[++tot]=i;
20         for (int j=1; j<=tot && i*p[j]<=n; j++){
21             b[i*p[j]]=1;
22             if (i%p[j]==0) break;
23         }
24     }
25 }
26 
27 int D(ll pi,ll pi1){
28     int s1=ksm(n-n/pi,k,mod-1),s2=ksm(n-n/pi1,k,mod-1);
29     return (s1-s2+mod-1)%(mod-1);
30 }
31 
32 int main(){
33     scanf("%d%d",&n,&k); init(); ans=1;
34     rep(i,1,tot)
35         for (ll t=p[i]; t<=n; t*=p[i])
36             ans=1ll*ans*ksm(t-t/p[i],D(t*p[i],t),mod)%mod;
37     printf("%d
",ans);
38     return 0;
39 }