【bzoj3561】DZY Loves Math VI

  • 本文为博主原创,未经许可不得转载

大力推一波:

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
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 500100
#define cadd(a,b) a=add(a,b)
#define csub(a,b) a=sub(a,b)
#define cmul(a,b) a=mul(a,b)
using namespace std;
const int mod=1e9+7;
int n,m,ans,cnt,check[MAXN],prime[MAXN],mu[MAXN],val[MAXN],sum[MAXN];
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline int sub(int a,int b){return (a-=b)<0?a+mod:a;}
inline int mul(int a,int b){return 1LL*a*b%mod;}
inline int power(int a,int b){
int ret=1;
while(b){
if(b&1) cmul(ret,a);
cmul(a,a); b>>=1;
}return ret;
}
void Init(){
int N=500000; mu[1]=1;
for(int i=2;i<=N;++i){
if(!check[i]) prime[++cnt]=i,mu[i]=sub(0,1);
for(int j=1;j<=cnt&&prime[j]*i<=N;++j){
check[prime[j]*i]=1;
if(i%prime[j]==0) {mu[prime[j]*i]=0; break;}
else mu[prime[j]*i]=sub(0,mu[i]);
}
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
scanf("%d%d",&m,&n); if(n<m) swap(n,m); Init();
for(int i=1;i<=n;++i) val[i]=1;
for(int k=1;k<=n;++k){
int ret=0;
for(int i=1;i<=(n/k);++i){
val[i]=mul(val[i],i);//val[i]表示i^k
sum[i]=add(sum[i-1],val[i]);
}
for(int d=1;d<=(n/k);++d)
cadd(ret,mul(sum[n/(k*d)],mul(sum[m/(k*d)],mul(mu[d],mul(val[d],val[d])))));
cadd(ans,mul(ret,power(k,k)));
}
printf("%d\n",ans);
return 0;
}
文章目录
,