关键词：
【BZOJ4816】[Sdoi2017]数字表格
Description
Input
有多组测试数据。
Output
Sample Input
2 3
4 5
6 7
Sample Output
6
960
题解：
然后O(nlogn)预处理g(i)即可。
P.S.：最后一行打错了，d应该是D。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const int maxn=1000010;
int N=1000000,num;
ll ans;
ll f[maxn],f1[maxn],g[maxn],sg[maxn],sg1[maxn];
int mu[maxn],pri[maxn/10];
bool np[maxn];
ll pm(ll x,ll y)
{
ll z=1;
while(y)
{
if(y&1) z=z*x%mod;
x=x*x%mod,y>>=1;
}
return z;
}
void init()
{
int i,j;
mu[1]=1;
f[0]=0,f[1]=f1[1]=1;
for(i=2;i<=N;i++)
{
f[i]=(f[i-2]+f[i-1])%mod,f1[i]=pm(f[i],mod-2);
if(!np[i]) pri[++num]=i,mu[i]=-1;
for(j=1;j<=num&&i*pri[j]<=N;j++)
{
np[i*pri[j]]=1;
if(i%pri[j]==0) break;
mu[i*pri[j]]=-mu[i];
}
}
for(i=1;i<=N;i++) g[i]=1;
for(i=1;i<=N;i++)
{
for(j=1;i*j<=N;j++)
{
if(mu[j]==1) g[i*j]=g[i*j]*f[i]%mod;
if(mu[j]==-1) g[i*j]=g[i*j]*f1[i]%mod;
}
}
sg[0]=sg1[0]=1;
for(i=1;i<=N;i++) sg[i]=sg[i-1]*g[i]%mod,sg1[i]=pm(sg[i],mod-2);
}
void work()
{
int n,m,i,last;
scanf("%d%d",&n,&m);
if(n>m) swap(n,m);
ans=1;
for(i=1;i<=n;i=last+1)
{
last=min(n/(n/i),m/(m/i));
ans=ans*pm(sg[last]*sg1[i-1]%mod,(ll)(n/i)*(m/i))%mod;
}
printf("%lld\n",ans);
}
int main()
{
init();
int T;
scanf("%d",&T);
while(T--) work();
return 0;
}
bzoj4816:[sdoi2017]数字表格
二次联通门: BZOJ4816:[Sdoi2017]数字表格 /*BZOJ4816:[Sdoi2017]数字表格莫比乌斯反演妈呀，我的μ没有啦*/#include<cstdio>#include<iostream>#definergregister#defineMax1000050#definemo1000000007 查看详情
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& 查看详情
bzoj4816[sdoi2017]数字表格(代码片段)
题面https://www.lydsy.com/JudgeOnline/problem.php?id=4816题解显然是莫比乌斯反演首先得出然后发现我们要把d提出去这样就好做了跟SDOI2015的一道题类似因为$leftlfloorfracnpightfloorleftlfloorfracmpightfloor$只有$(sqrtn+sqrtm)$种取 查看详情
bzoj4816数字表格
...函数，话说上次考莫比鸟斯就是去年吧，好像题目名也叫数字表格，只不过多了一个前缀"Crash的"。慢慢推吧， 查看详情
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 查看详情
[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]数字表格
题面戳我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 查看详情
bzoj4816sdoi2017数字表格(代码片段)
一开始只推出O(TN)的做法，后来看了看发现再推一步就好了。我们只需要枚举gcd就可以啦。然后我们改变一下枚举顺序 设T为dk预处理中间那部分前缀积就好了。1#include<bits/stdc++.h>2usingnamespacestd;3constintN=1e6+10,mod=1e9+7;4intn,m,... 查看详情
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]}$$然后反演得... 查看详情
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 查看详情
[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 查看详情
学术篇sdoi2017数字表格
======传======送======门======在======里======面======去年忘记可以预处理了...然后就打了10pts的暴力...现在学了莫比乌斯反演就可以来做了=======================================这个题目看着非常的简单,就是要求这个式子[prod_{i=1}^Nprod_{j=1}^Mf[gcd... 查看详情
bzoj2154crash的数字表格（莫比乌斯反演）
【BZOJ2154】Crash的数字表格（莫比乌斯反演）题面BZOJ简化题意：给定(n,m)求[sum_{i=1}^nsum_{j=1}^mlcm(i,j)]题解以下的一切都默认(n<m)我们都知道(lcm(i,j)=frac{ij}{gcd(i,j)})所以所求化简[sum_{i=1}^nsum_{j=1}^mfrac{ij}{gcd(i,j)}]看到(g 查看详情