正文

[sdoi2017]数字表格

日拱一卒功不唐捐  日拱一卒功不唐捐  2022-08-27  295

关键词：

[Sdoi2017]数字表格

http://www.lydsy.com/JudgeOnline/problem.php?id=4816

Time Limit: 50 Sec Memory Limit: 128 MB

Description

Doris刚刚学习了fibonacci数列。用f[i]表示数列的第i项，那么

f[0]=0

f[1]=1

f[n]=f[n-1]+f[n-2],n>=2

Doris用老师的超级计算机生成了一个n×m的表格，第i行第j列的格子中的数是f[gcd(i,j)]，其中gcd(i,j)表示i,

j的最大公约数。Doris的表格中共有n×m个数，她想知道这些数的乘积是多少。答案对10^9+7取模。

Input

有多组测试数据。

第一个一个数T，表示数据组数。

接下来T行，每行两个数n,m

T<=1000,1<=n,m<=10^6

Output

输出T行，第i行的数是第i组数据的结果

Sample Input

3
2 3
4 5
6 7

Sample Output

1
6
960

g（d）转化为 POI 2007 Zap

题目即解释参考 http://www.cnblogs.com/TheRoadToTheGold/p/6609495.html

转化提示：1、a^b * c^b = (a*c)^d

2、a^(b*c) = (a^b)^c

预处理g的时候会遇到 mul=-1，所以要处理逆元

#include<cstdio>
#include<iostream>
#define N 1000101
using namespace std;
int mul[N],prime[N],cnt;
long long f[N],g[N],inver[N];
const int mod=1e9+7;
bool v[N];
int n,m;
long long mult(long long a,long long b )
{
    long long ans=1;
    for(;b;b>>=1,a=a*a%mod)
     if(b&1) ans=ans*a%mod;
    return ans;
}
void pre()
{
    mul[1]=1;
    for(int i=2;i<N;i++)
    {
        if(!v[i])
        {
            prime[++cnt]=i;
            mul[i]=-1;
        }
        for(int j=1;j<=cnt;j++)
        {
            if(prime[j]*i>N-1) break;
            v[i*prime[j]]=true;
            if(i%prime[j]==0) break;
            mul[i*prime[j]]=-mul[i];
        }
    }
    f[1]=1;
    for(int i=2;i<N;i++) f[i]=(f[i-1]+f[i-2])%mod;
    for(int i=1;i<N;i++) inver[i]=mult(f[i],mod-2);
    fill(g,g+N,1);
    for(int i=1;i<N;i++)
     for(int j=1;i*j<N;j++)
      if(mul[j])  g[i*j]= g[i*j]*(mul[j]==1 ? f[i] : inver[i])%mod;
    for(int i=1;i<N;i++) g[i]=g[i-1]*g[i]%mod;
}
void solve()
{
    long long ans=1;int j;
    if(n>m) swap(n,m);
    for(int i=1;i<=n;i=j+1)
    {
        j=min(n/(n/i),m/(m/i));
        ans=ans*mult(g[j]*mult(g[i-1],mod-2)%mod,(long long)(n/i)*(m/i))%mod;
    }
    printf("%lld\n",ans);
}
int main()
{
    /*freopen("product.in","r",stdin);
    freopen("product.out","w",stdout);*/
	pre();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        solve();
    }
}

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 查看详情

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... 查看详情

[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的最... 查看详情

[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[ 查看详情

bzoj4816[sdoi2017]数字表格(代码片段)

题面https://www.lydsy.com/JudgeOnline/problem.php?id=4816题解显然是莫比乌斯反演首先得出然后发现我们要把d提出去这样就好做了跟SDOI2015的一道题类似因为$leftlfloorfracnpightfloorleftlfloorfracmpightfloor$只有$(sqrtn+sqrtm)$种取查看详情

codevs5962[sdoi2017]数字表格

输入描述 InputDescription [题解]对于蓝色部分预处理前缀积。然后在用除法分块搞一下。O(Q*sqrt(min(n,m))*logn+nlogn)#include<cstdio>#include<iostream>usingnamespacestd;typedeflonglongll;constintN=1e6+5;constllmod= 查看详情

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]数字表格(莫比乌斯反演)(代码片段)

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]数字表格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]数字表格

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$列的格子中的查看详情

[sdoi2017]数字表格(代码片段)

DescriptionDoris刚刚学习了fibonacci数列。用f[i]表示数列的第i项，那么\[f(x)=\begincases0&,x=0\nonumber\\1&,x=1\nonumber\\f(x-1)+f(x-2)&,x\geqslant2\nonumber\endcases\]Doris用老师的超级计算机生成了一个n×m的表格，第i行第j列的格子中的查看详情

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# 查看详情

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 查看详情

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& 查看详情

[sdoi2017]数字表格(代码片段)

又一道没有做出来的题首先做最基础的mobius反演，可以得到，答案就是一堆fi^k乘起来，k是下面这个东西。套路的用T代替id，并枚举T。指数的式子变成π(i|T)mu（T/i）?（n/T）?（m/T）考虑先枚举指数再枚举i（没想到这一步！）令dp[... 查看详情