【bzoj4816】数字表格

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

设$f(n)=\sum_{d|n} g(d)$

则$g(n)=\frac{f(n)}{\sum_{d|n且d\neq n} g(d)}$

f和g都可以递推求出

$ans=\sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{d|i且d|j} f(gcd(i,j))$

$ans=\sum_{d=1}^{min(n,m)}g(d)^{\left [ \frac{n}{d} \right ]\left [ \frac{m}{d} \right ]}$

注意到$\left [ \frac{n}{d} \right ]\left [ \frac{m}{d} \right ]$只有最多$\sqrt n+\sqrt m$个取值

所以可以分块优化

感觉这个g函数设置的好玄妙啊！

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
#include<bits/stdc++.h>
#define FILE "read"
using namespace std;
typedef long long ll;
const int mod=(int)1e9+7,MAXN=(int)1e6,D=50;
ll g[MAXN+D],sum[MAXN+D],sumv[MAXN+D];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
ll fast(ll a,ll b){ll temp(1);for(;b;b>>=1,a=a*a%mod)if(b&1)temp=temp*a%mod;return temp;}
void pre(){
	g[1]=1; for(int i=2;i<=MAXN;++i) g[i]=(g[i-1]+g[i-2])%mod;
	for(int i=1;i<=MAXN;++i){
		ll temp=fast(g[i],mod-2);
		for(int j=(i<<1);j<=MAXN;j+=i)
			g[j]=g[j]*temp%mod;
	}
	sum[0]=1;  for(int i=1;i<=MAXN;++i) sum[i]=sum[i-1]*g[i]%mod;
	sumv[0]=1; for(int i=1;i<=MAXN;++i)  sumv[i]=fast(sum[i],mod-2);
}
void solve(){
	int n=read(),m=read(),last; ll ans(1);
	if(n>m)  swap(n,m);
	for(int i=1;i<=n;i=last+1){
		last=min(n/(n/i),m/(m/i));
		ans=ans*fast(sum[last]*sumv[i-1]%mod,(ll)(n/i)*(m/i))%mod;
	}
	printf("%lld\n",ans);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	pre(); for(int T=read();T;--T) solve();
	return 0;
}

本文标题:【bzoj4816】数字表格

文章作者:chty

发布时间:2017年04月11日 - 19时56分

最后更新:2018年03月02日 - 17时14分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,