考虑一个数对于整个区间的贡献,发现就是把其所有不同的质因子容斥一下,注意这个小因子的容斥是整个区间,但是我们只要[num+1,n]这段区间的答案,所以再减掉[1,num]这里的容斥即可.

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
int   vis[100000010];//存最小质因数,负的表示质数表中的位置(负的)
int  p[10000010],ptop=0;//存质数 
void sieve(int n){//[1,n]
	int tmp;
	for(int i=2;i<=n;++i){
		if(!vis[i]){
			vis[i]=-(++ptop);
			p[ptop]=i;
		}
		for(int j=1;j<=ptop&&i*p[j]<=n;++j){
			vis[i*p[j]]=p[j];
			if(i%p[j]==0){
				break;
			}else{
			}
		}
	}
}
const int mod=1e9+7;
template<typename T1,typename T2,typename T3>
T1 qp(T1 b,T2 po,T3 p){
	T1 res(1);
	while(po>0){
		if(po&1)
			res=res*b%p;
		b=b*b%p;
		po>>=1;
	}
	return res;
}
long long n,m,res;
int st[1000],top=0;

void dfs(int& res,int num,int bi,int top,int cnt,int prod){
	if(num>top){
		if(cnt&1){
			res-=(n/prod-bi/prod);
		}else{
			res+=(n/prod-bi/prod);
		}
		return;
	}
	dfs(res,num+1,bi,top,cnt,prod);
	dfs(res,num+1,bi,top,cnt+1,prod*st[num]);
}
int calc(int num){
	int ttmp=num;
	top=0;
	while(1){
		if(vis[num]<=0){
			st[++top]=p[-vis[num]];
			break;
		}else{
			st[++top]=vis[num];
			num/=vis[num];
		}
	}
	sort(st+1,st+top+1);
	top=unique(st+1,st+top+1)-st-1;
	int res=0;
	dfs(res,1,ttmp,top,0,1);
	return res;
}

//#define NaraFluorine
int main(){
	n=100000000;
	sieve(n);
	res=1;
	for(i64 i=2;i<=n;++i){
		int po=calc(i);
		res*=qp(i,po,mod);
		res%=mod;
		if(i%1000000==0){
			fout<<i<<"\n";
			fout.flush();
		}
	}
	fout<<res<<"\n";
	return 0;
}