关键词：
题面
https://www.lydsy.com/JudgeOnline/problem.php?id=4816
题解
显然是莫比乌斯反演
首先得出
然后发现 我们要把d提出去
这样就好做了
跟SDOI2015的一道题类似
因为 $left lfloor fracnp ight floor left lfloor fracmp ight floor$只有$(sqrt n +sqrt m)$种取值 并且$prod_k|p f[k]^mu(fracpk)$对于每个p都是固定的
所以我们可以预处理$prod_k|p f[k]^mu(fracpk)$的前缀积 以及前缀积的逆元 这样可以方便的算出区间的乘积
然后对于每一组询问 我们枚举$(sqrt n +sqrt m)$种取值 就可以得出结果
Code
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 5 ll read() 6 ll x=0,f=1;char c=getchar(); 7 while(c<‘0‘ || c>‘9‘)if(c==‘-‘)f=-1;c=getchar(); 8 while(c>=‘0‘ && c<=‘9‘)x=x*10+c-‘0‘;c=getchar(); 9 return x*f; 10 11 12 const int maxn=1000100; 13 const int mod=1e9+7; 14 int mu[maxn],pr[maxn],cnt; 15 bool isp[maxn]; 16 int fib[maxn],g[maxn],G[maxn],invG[maxn]; 17 int fpw[maxn][3]; 18 19 int ksm(int a,int b) 20 int ret=1; 21 for(int i=0;i<=30;i++) 22 if(b&1) ret=ret*1ll*a%mod; 23 a=a*1ll*a%mod; 24 b=b>>1; 25 if(b==0) return ret; 26 27 28 29 int inv(int a) 30 return ksm(a,mod-2); 31 32 33 int main() 34 #ifdef LZT 35 freopen("in","r",stdin); 36 #endif 37 mu[1]=1; 38 memset(isp,1,sizeof(isp)); 39 for(int i=2;i<=1000000;i++) 40 if(isp[i]) 41 pr[++cnt]=i; 42 mu[i]=-1; 43 44 for(int j=1;j<=cnt && i*pr[j]<=1000000;j++) 45 isp[i*pr[j]]=0; 46 if(i%pr[j]==0) break; 47 mu[i*pr[j]]=-mu[i]; 48 49 50 51 fib[1]=1; 52 for(int i=2;i<=1000000;i++) 53 fib[i]=(fib[i-1]+fib[i-2])%mod; 54 for(int i=1;i<=1000000;i++) 55 fpw[i][0]=inv(fib[i]); 56 fpw[i][1]=1; 57 fpw[i][2]=fib[i]; 58 59 60 for(int i=1;i<=1000000;i++) 61 g[i]=1; 62 for(int k=1;k*k<=i;k++) 63 if(i%k) continue; 64 g[i]=g[i]*1ll*fpw[k][mu[i/k]+1]%mod; 65 if(k*k!=i) g[i]=g[i]*1ll*fpw[i/k][mu[k]+1]%mod; 66 67 68 G[0]=1; 69 for(int i=1;i<=1000000;i++) 70 G[i]=G[i-1]*1ll*g[i]%mod; 71 72 invG[0]=1; 73 for(int i=1;i<=1000000;i++) 74 invG[i]=inv(G[i]); 75 76 int tc=read(); 77 while(tc--) 78 int n=read(),m=read(); 79 int j; 80 int ans=1; 81 for(int i=1;i<=min(n,m);i=j+1) 82 j=min(n/(n/i),m/(m/i)); 83 ans=ans*1ll*ksm(G[j]*1ll*invG[i-1]%mod,(n/i)*1ll*(m/i)%(mod-1))%mod; 84 85 printf("%d ",ans); 86 87 88 return 0; 89
Review
推导不成功 我自己没有推出来
枚举取值的写法:
1 int j; 2 for(int i=1;i<=min(n,m);i=j+1) 3 j=min(n/(n/i),m/(m/i)); 4 //...... 5
[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]数字表格
题目链接bzoj4816:[Sdoi2017]数字表格题解满满的反演的套路的味道\[Ans=\prod_i=1^n\prod_j=1^mf[gcd(i,j)]\]常规操作枚举约数\[\prod_d=1^n\prod_i=1^n\prod_j=1^mgcd(i,j)==d\?\f[gcd(i,j)]\]上面的式子可以化为\[\prod_d=1^nf[d]^\su 查看详情
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,... 查看详情
[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]数字表格
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 查看详情
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]}$$然后反演得... 查看详情
[sdoi2017]数字表格(代码片段)
SOL： 怎么说呢,套路题。随便数论分块就好了//luogu-judger-enable-o2#include<bits/stdc++.h>#defineN1000007#defineLLlonglong#defineprip#definemo1000000007usingnamespacestd;intpri[N/10],tot,u[N],usd[N];LLf[N],ff[ 查看详情
sdoi2017数字表格(代码片段)
题目描述：f为斐波那契数列。T组询问，每次给出表格的n、m。表中(i,j)为gcd(i,j)，求表中所有数之积mod1e9+7的值。T<=1e5,n,m<=1e9题解：反演。代码：#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;#defineN1000500# 查看详情