YbtOJ 915「欧拉函数」欧拉欧拉

(Updated: )
oi
,

题目链接：YbtOJ #915

小 A 有两个正整数 $n,k$。

规定一个正整数序列 $a$ 是合法的，当且仅当它的长度为 $k$，且序列中的每一个 $a_i$ 都小于等于 $n$。

由于小 A 特别喜欢欧拉，他定义一个序列 $a$ 的权值 $F(a)=\phi(\operatorname{lcm}(a_1,a_2,\cdots,a_k))$。

现在，小 A 希望你求出 所有合法序列的权值之积 在模 $10^9+7$ 意义下的值。

$1\le n,k\le 10^6$。

Solution

题目即求：
$$
\prod_{i_1=1}^n\prod_{i_2=1}^n\cdots\prod_{i_n=1}^n\phi(\operatorname{lcm}(i_1,i_2,\cdots,i_n))
$$
把欧拉函数拆开，不妨以每个质数 $p$ 考虑，不妨设 $\forall j\in [1,n],p^{c_j}i_j$，且 $c=\max_{j=1}^n c_j$。

显然有 $p^c\operatorname{lcm}$ 且 $p^{c+1}\operatorname{lcm}$。

我们又知道：
$$
\phi(p^c)=(p-1)p^{c-1}
$$

  • 考虑 $(p-1)$ 的贡献，由于若 $\exists j\in [1,n], pi_j$，则该贡献就会被乘上，于是它的总贡献为：$(p-1)^{n^k-(n-\lfloor \frac np \rfloor)^k}$。
  • 考虑 $p^{c-1}$ 的贡献，考虑暴枚 $c$，显然时间复杂度为 $\log$ 左右的，可以接受，总贡献为：$\prod_{j\ge 2\land p^j \leq n}p^{n^k-(n-\lfloor \frac n{p^j} \rfloor)^k}$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define int long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    #define FS 100000
    #define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
    #define pc(c) (FC==FE&&(clear(),0),*FC++=c)
    int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
    I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
    Tp I void read(Ty& x) {x=0;RI f=1;W(!isdigit(oc=tc())) f=oc^'-'?1:-1;W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));x*=f;}
    Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
    Tp I void write(Ty x) {x<0&&(pc('-'),x=-x);W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);}
    Tp I void writeln(Ty x) {x<0&&(pc('-'),x=-x);W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
Cn int N=1e6+10,mod=1e9+7;
int n,k,Mul,p[N],cnt,v[N],Ans=1;
I void Pre(){RI i,j;for(i=2;i<=n;i++) for(!v[i]&&(p[++cnt]=i),j=1;j<=cnt&&i*p[j]<=n;j++) if(v[i*p[j]]=1,!(i%p[j])) break ;}
I int QP(RI a,RI b,CI p){a%=p;RI s=1;W(b) b&1&&(s=1LL*s*a%p),a=1LL*a*a%p,b>>=1;return s;}
I int Phi(RI x){
    RI i,X=x;for(i=2;i*i<=x;i++) if(!(x%i)){
        X=X/i*(i-1);W(!(x%i)) x/=i; 
    }x>1&&(X=X/x*(x-1));return X;
}
signed main(){
    freopen("euler.in","r",stdin),freopen("euler.out","w",stdout);
    RI i,j,phi;for(read(n,k),Pre(),phi=Phi(mod),i=1;i<=cnt;i++){
        Ans=1LL*Ans*QP(p[i]-1,(QP(n,k,phi)+phi-QP(n-(n/p[i]),k,phi))%phi,mod)%mod;
        for(j=n/p[i]/p[i];j;j/=p[i]) Ans=1LL*Ans*QP(p[i],(QP(n,k,phi)+phi-QP(n-j,k,phi))%phi,mod)%mod;
    }return writeln(Ans),clear(),0;
}