关键词：
4816: [Sdoi2017]数字表格
Time Limit: 50 Sec Memory Limit: 128 MB
Submit: 1259 Solved: 625
[Submit][Status][Discuss]Description
Doris刚刚学习了fibonacci数列。用f[i]表示数列的第i项，那么f[0]=0f[1]=1f[n]=f[n-1]+f[n-2],n>=2Doris用老师的超级计算机生成了一个n×m的表格，第i行第j列的格子中的数是f[gcd(i,j)]，其中gcd(i,j)表示i,j的最大公约数。Doris的表格中共有n×m个数，她想知道这些数的乘积是多少。答案对10^9+7取模。Input
有多组测试数据。
第一个一个数T，表示数据组数。接下来T行，每行两个数n,mT<=1000,1<=n,m<=10^6Output
输出T行，第i行的数是第i组数据的结果Sample Input
3
2 3
4 5
6 7
Sample Output
1
6
960HINT
Source
[Submit][Status][Discuss]
不知道为什么要用fibonacci，感觉既没有用到矩乘又没有用到$gcd(f[i],f[j])=f[gcd(i,j)]$的性质。
首先列出连乘式，可以发现很像莫比乌斯反演，先试着推一下式子，从每个数出现的次数入手。
$$Ans(n,m)=\prod_df(d)^\sum_i=1^n\sum_j=1^m[(i,j)=d]=\prod_d=1^\min(n,m)f(d)^\sum_p=1^\frac\min(n,m)d\mu(d)\lfloor \fracnpd\rfloor \lfloor\fracmpd\rfloor$$
到这里，有一种错误的想法（没错就是我误以为可以拿60分的想法）：
设$$g(n,m,d)=\sum_i=1^\min(n,m)\mu(d)\lfloor \fracni \rfloor \lfloor \fracmi\rfloor$$
这样$$Ans(n,m)=\prod_d=1^\lfloor \frac\min(n,m)d \rfloorf(d)^g(\lfloor \fracnd \rfloor \lfloor \fracmd \rfloor,d)$$
这个看上去用分块优化可以做到$$\beginalignedO(T\int_1^n\sqrt\fracnxdx)& =O(T\sqrtn\int_1^n\sqrt\frac1xdx)\\ & =O(2T\sqrtn\sqrtn)\\ & =O(Tn)\endaligned$$但实际上由于分块区间不连续，复杂度是不对的。
那么我们继续化简刚才的式子：
$$\beginalignedAns(n,m)& =\prod_d=1^\min(n,m)f(d)^\sum_d|T^\min(n,m)\mu(\fracTd)\lfloor \fracnT \rfloor \lfloor \fracmT\rfloor\\ & =\prod_T=1^\min(n,m)\prod_d|Tf(d)^\mu(\fracTd)\lfloor \fracnT \rfloor\lfloor\fracmT\rfloor\\ & =\prod_T=1^\min(n,m)g(T)^\lfloor\fracnT\rfloor\lfloor\fracmT\rfloor\endaligned$$ $g(T)$可以预处理出来，这样总复杂度就是$O(n\log n+T\sqrt\min(n,m))$了。
注意$\mu$在指数上时会有$-1$，这个要求逆元，如果先预处理所有$f[i]$的逆元的话会快一倍。
这道题总体并不难，主要就是将莫比乌斯反演中的一些套路从加法变成乘法了，实现的时候有几个细节注意一下就好。
（以后再也不手写LaTeX莫比乌斯反演的题解了）
1 #include<cstdio> 2 #include<algorithm> 3 #define rg register int 4 #define rep(i,l,r) for (rg i=l; i<=r; i++) 5 typedef long long ll; 6 using namespace std; 7 8 const int N=1000100,mod=1000000007; 9 bool b[N]; 10 int n,m,T,ans,tot,p[N],f[N],g[N],G[N],G1[N],miu[N],F[N][3]; 11 12 int ksm(int a,int b) 13 int res; 14 for (res=1; b; a=1ll*a*a%mod,b>>=1) 15 if (b & 1) res=1ll*res*a%mod; 16 return res; 17 18 19 void pre() 20 miu[1]=1; 21 for (rg i=2; i<N; i++) 22 if (!b[i]) p[++tot]=i,miu[i]=-1; 23 for (rg j=1; j<=tot && p[j]*i<N; j++) 24 rg t=p[j]*i; b[t]=1; 25 if (i%p[j]) miu[t]=-miu[i]; else break; 26 27 28 for (rg i=1; i<N; i++) g[i]=1,F[i][0]=ksm(f[i],mod-2),F[i][1]=1,F[i][2]=f[i]; 29 for (rg i=1; i<N; i++) 30 for (rg j=i; j<N; j+=i) 31 g[j]=1ll*g[j]*F[i][miu[j/i]+1]%mod; 32 G[0]=1; G[1]=g[1]; for (int i=2; i<N; i++) G[i]=1ll*G[i-1]*g[i]%mod; 33 G1[N-1]=ksm(G[N-1],mod-2); for (int i=N-2; ~i; i--) G1[i]=1ll*G1[i+1]*g[i+1]%mod; 34 35 36 int main() 37 freopen("product.in","r",stdin); 38 freopen("product.out","w",stdout); 39 f[1]=1; for (rg i=2; i<N; i++) f[i]=(f[i-1]+f[i-2])%mod; 40 pre(); 41 for (scanf("%d",&T); T--; ) 42 scanf("%d%d",&n,&m); rg lst=0; 43 if (n>m) swap(n,m); ans=1; 44 for (rg i=1; i<=n; i=lst+1) 45 lst=min(n/(n/i),m/(m/i)); 46 ans=1ll*ans*ksm(1ll*G[lst]*G1[i-1]%mod,1ll*(n/i)*(m/i)%(mod-1))%mod; 47 48 printf("%d\n",ans); 49 50 return 0; 51
bzoj4816[sdoi2017]数字表格(代码片段)
题面https://www.lydsy.com/JudgeOnline/problem.php?id=4816题解显然是莫比乌斯反演首先得出然后发现我们要把d提出去这样就好做了跟SDOI2015的一道题类似因为$leftlfloorfracnpightfloorleftlfloorfracmpightfloor$只有$(sqrtn+sqrtm)$种取 查看详情
[bzoj4816][sdoi2017]数字表格
[BZOJ4816][Sdoi2017]数字表格试题描述Doris刚刚学习了fibonacci数列。用f[i]表示数列的第i项，那么f[0]=0f[1]=1f[n]=f[n-1]+f[n-2],n>=2Doris用老师的超级计算机生成了一个n×m的表格，第i行第j列的格子中的数是f[gcd(i,j)]，其中gcd(i,j)表示i,j的最... 查看详情
bzoj4816:[sdoi2017]数字表格
问题： [n/k]/d==[n/(kd)]; 线性筛正确性证明 这么求逆元Right？a=k*p; 1LL转化作用域 longlong做数组下标#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;typedeflonglongLint;constintmaxn=100 查看详情
bzoj4816:[sdoi2017]数字表格
DescriptionDoris刚刚学习了\(fibonacci\)数列。用\(f[i]\)表示数列的第\(i\)项，那么\[\beginalignf[0]&=0\\f[1]&=1\\f[n]&=f[n-1]+f[n-2],n>=2\endalign\]Doris用老师的超级计算机生成了一个\(n\timesm\)的表格，第\(i\)行第\(j\)列的格子中的 查看详情
[bzoj4816][sdoi2017]数字表格(莫比乌斯反演)(代码片段)
4816:[Sdoi2017]数字表格TimeLimit:50Sec MemoryLimit:128MBSubmit:1259 Solved:625[Submit][Status][Discuss]DescriptionDoris刚刚学习了fibonacci数列。用f[i]表示数列的第i项，那么f[0]=0f[1]=1f[n]=f[n-1]+f[n-2] 查看详情
bzoj4816[sdoi2017]数字表格
TimeLimit: 50Sec MemoryLimit: 128MBSubmit: 646 Solved: 296DescriptionDoris刚刚学习了fibonacci数列。用f[i]表示数列的第i项，那么f[0]=0f[1]=1f[n]=f[n-1]+f[n-2],n>=2Doris用老师的超级计算 查看详情
bzoj4816[sdoi2017]数字表格莫比乌斯反演
【BZOJ4816】[Sdoi2017]数字表格DescriptionDoris刚刚学习了fibonacci数列。用f[i]表示数列的第i项，那么f[0]=0f[1]=1f[n]=f[n-1]+f[n-2],n>=2Doris用老师的超级计算机生成了一个n×m的表格，第i行第j列的格子中的数是f[gcd(i,j)]，其中gcd(i,j)表示i,... 查看详情
bzoj4816:[sdoi2017]数字表格
题面戳我Sol摆公式：(ans=Pi_{i=1}^{n}Pi_{j=1}^{m}f[gcd(i,j)])考虑每个gcd的贡献，设n<m则就是(Pi_{d=1}^{n}Pi_{i=1}^{lfloorfrac{n}{d} floor}Pi_{j=1}^{lfloorfrac{m}{d} floor}f[d]*[gcd(i,j)==1])(=Pi_{d=1}^{ 查看详情
bzoj4816[sdoi2017]数字表格
题目链接以下除法均指下取整[prod_{i=1}^nprod_{j=1}^mf(gcd(i,j))=prod_{x}f(x)^{sum_isum_j[gcd(i,j)=x]}=prod_{x}f(x)^{sum_{x|d}mu(frac{d}{x})frac{n}{d}frac{m}{d}}=prod_{d}(prod_{x|d}f(x)^{mu(frac{d 查看详情
bzoj.4816.[sdoi2017]数字表格(莫比乌斯反演)(代码片段)
题目链接总感觉博客园的\(Markdown\)很。。\(gouzhi\)，可以看这的。这个好像简单些啊，只要不犯sb错误\(Description\) 用\(f[i]\)表示\(Fibonacci\)数列的第\(i\)项，求\[\prod_i=1^n\prod_j=1^mf[\gcd(i,j)]\mod(10^9+7)\]\(Solution\)\[\beginalignedAns& 查看详情
bzoj4816sdoi2017数字表格(代码片段)
一开始只推出O(TN)的做法，后来看了看发现再推一步就好了。我们只需要枚举gcd就可以啦。然后我们改变一下枚举顺序 设T为dk预处理中间那部分前缀积就好了。1#include<bits/stdc++.h>2usingnamespacestd;3constintN=1e6+10,mod=1e9+7;4intn,m,... 查看详情
sdoi2017round1day1题解（bzoj4816bzoj4817bzoj4818）
不知道有几个AK的，除了出题人SB搬了个BZOJ3779以外，应该没什么因素阻碍AK吧。要是SCOI考这套题多好。BZOJ4816数字表格SB反演，推出$ans=prod_{i=1}^nf^{sum_{j=1}^{leftlfloorfracni ight floor}mu(j)leftlfloorfracn{ij} ight floorleftlfloorfrac 查看详情
bzoj4816数字表格
...函数，话说上次考莫比鸟斯就是去年吧，好像题目名也叫数字表格，只不过多了一个前缀"Crash的"。慢慢推吧， 查看详情
[sdoi2017]数字表格
[Sdoi2017]数字表格http://www.lydsy.com/JudgeOnline/problem.php?id=4816TimeLimit: 50Sec MemoryLimit: 128MBDescriptionDoris刚刚学习了fibonacci数列。用f[i]表示数列的第i项，那么f[0]=0f[1]=1f[n]=f[n-1]+f[n-2 查看详情
bzoj4816数字表格（莫比乌斯反演）
【BZOJ4816】数字表格（莫比乌斯反演）题面BZOJ求[prod_{i=1}^nprod_{j=1}^mf[gcd(i,j)]]题解忽然不知道这个要怎么表示。。。就写成这样吧。。[prod_{d=1}^nprod_{i=1}^nprod_{j=1}^mif(gcd(i,j)==d)f[gcd(i,j)]]直接把(f[d])提出来[prod_{d=1}^{n}f[d]^ 查看详情
[bzoj4816]数字表格莫比乌斯反演
第一次见到这种形式，推了两步就被卡住了。没想到还能这么迁移QAQ，真强！题目设$f(i)$为第$i$项斐波那契数列要求计算$$ans=prod_{i=1}^nprod_{j=1}^mf(gcd(i,j))$$枚举$d=gcd$得到$$ans=prod_{d=1}^nf(d)^{sum_{i=1}^nsum_{j=1}^m[gcd(i,j)==d]}$$然后反演得... 查看详情
p3704[sdoi2017]数字表格
#include<iostream>#include<cstdio>#include<cstring>#defineLLlonglong#definemaxn1000009#defineNmaxn+10#defineM1000000007usingnamespacestd;intn,m;intq;LLksm(LLa,LLp){ LLans=1; for(;p;p 查看详情
学术篇sdoi2017数字表格
======传======送======门======在======里======面======去年忘记可以预处理了...然后就打了10pts的暴力...现在学了莫比乌斯反演就可以来做了=======================================这个题目看着非常的简单,就是要求这个式子[prod_{i=1}^Nprod_{j=1}^Mf[gcd... 查看详情