BZOJ 4816 [Sdoi2017]数字表格_「sdoi2017」数字表格-程序员宅基地

技术标签: 莫比乌斯反演  

题目链接

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

题解

反演
∏ T = 1 min ⁡ ( n , m ) ( ∏ d ∣ T f i b ( d ) μ ( d ) ) ⌊ n / d ⌋ ⌊ m / d ⌋ \prod_{T=1}^{\min(n,m)}(\prod_{d|T}fib(d)^{\mu(d)})^{\lfloor n/d\rfloor\lfloor m/d\rfloor} T=1min(n,m)(dTfib(d)μ(d))n/dm/d
预处理出中间部分,整除分块即可。

注意不要暴力算 f i b ( d ) fib(d) fib(d)的逆元,可以预处理出逆元。

代码

#include <cstdio>
#include <algorithm>

int read()
{
    
  int x=0,f=1;
  char ch=getchar();
  while((ch<'0')||(ch>'9'))
    {
    
      if(ch=='-')
        {
    
          f=-f;
        }
      ch=getchar();
    }
  while((ch>='0')&&(ch<='9'))
    {
    
      x=x*10+ch-'0';
      ch=getchar();
    }
  return x*f;
}

const int maxn=1000000;
const int mod=1000000007;
const int pmod=mod-1;

int quickpow(int a,int b)
{
    
  int res=1;
  while(b)
    {
    
      if(b&1)
        {
    
          res=1ll*res*a%mod;
        }
      a=1ll*a*a%mod;
      b>>=1;
    }
  return res;
}

int p[maxn+10],prime[maxn+10],cnt,mu[maxn+10],f[maxn+10],fib[maxn+10],ifib[maxn+10];

int getprime()
{
    
  p[1]=mu[1]=1;
  for(int i=2; i<=maxn; ++i)
    {
    
      if(!p[i])
        {
    
          prime[++cnt]=i;
          mu[i]=-1;
        }
      for(int j=1; (j<=cnt)&&(i*prime[j]<=maxn); ++j)
        {
    
          int x=i*prime[j];
          p[x]=1;
          if(i%prime[j]==0)
            {
    
              mu[x]=0;
              break;
            }
          mu[x]=-mu[i];
        }
    }
  fib[0]=ifib[0]=0;
  fib[1]=ifib[1]=1;
  for(int i=2; i<=maxn; ++i)
    {
    
      fib[i]=fib[i-1]+fib[i-2];
      if(fib[i]>=mod)
        {
    
          fib[i]-=mod;
        }
      ifib[i]=quickpow(fib[i],mod-2);
    }
  for(int i=0; i<=maxn; ++i)
    {
    
      f[i]=1;
    }
  for(int d=1; d<=maxn; ++d)
    {
    
      for(int T=d; T<=maxn; T+=d)
        {
    
          if(mu[T/d]==1)
            {
    
              f[T]=1ll*f[T]*fib[d]%mod;
            }
          else if(mu[T/d]==-1)
            {
    
              f[T]=1ll*f[T]*ifib[d]%mod;
            }
        }
    }
  for(int i=1; i<=maxn; ++i)
    {
    
      f[i]=1ll*f[i]*f[i-1]%mod;
    }
  return 0;
}

int T,n,m;

int main()
{
    
  getprime();
  T=read();
  while(T--)
    {
    
      n=read();
      m=read();
      int res=1;
      for(int l=1,r; l<=std::min(n,m); l=r+1)
        {
    
          r=std::min(n/(n/l),m/(m/l));
          res=1ll*res*quickpow(1ll*f[r]*quickpow(f[l-1],mod-2)%mod,1ll*(n/l)*(m/l)%pmod)%mod;
        }
      printf("%d\n",res);
    }
  return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/wang3312362136/article/details/86062256

智能推荐

【进阶版】机器学习之神经网络与深度学习基本知识和理论原理(07)_深度随机配置网络-程序员宅基地

文章浏览阅读931次。机器学习算法知识、数据预处理、特征工程、模型评估——原理+案例+代码实战机器学习之Python开源教程——专栏介绍及理论知识概述机器学习框架及评估指标详解Python监督学习之分类算法的概述数据预处理之数据清理,数据集成,数据规约,数据变化和离散化特征工程之One-Hot编码、label-encoding、自定义编码卡方分箱、KS分箱、最优IV分箱、树结构分箱、自定义分箱特征选取之单变量统计、基于模型选择、迭代选择机器学习八大经典分类万能算法——代码+案例项目开源、可直接应用于毕设+科研项目。_深度随机配置网络

python logging模块“另一个程序正在使用此文件,进程无法访问。”问题解决办法...-程序员宅基地

文章浏览阅读2.7k次。在多进程下使用python的logging模块,经常会遇到“另一个程序正在使用此文件,进程无法访问。”的错误。解决办法: https://github.com/Preston-Landers/concurrent-log-handlerpip install concurrent-log-handler To use this module from a logging config..._logging roatingfilehander 另一个程序正在使用此文件,进程无法访问

SPA与DPA 攻击【转】-程序员宅基地

文章浏览阅读624次。转自:http://blog.sina.com.cn/s/blog_6cb58dbf0102v7ym.htmlSPASPA是一种直接解释能量消耗测定值的技术。系统消耗能量的大小随微处理器执行的指令不同而不同, 当微处理器在对加密算法的不同部分执行运算时, 能量消耗变化有的会很明显。借助这种特征, 攻击者能区分出单条指令, 达到破解算法的目的。DPA..._spa攻击

python 对话框的创建及调用_Python使用tkinter界面编程中对话框样式汇总-程序员宅基地

文章浏览阅读625次。在GUI编程中,对话框是用户交互和检索信息的重要控件。今天,我们对tkinter中常用的对话框进行汇总。tkinter模块的子模块messagebox、filedialog、colorchooser、simpledialog中包括了一些常用的预定义好的对话框,当然也可以通过继承Toplevel创建自定义的对话框。如果对于界面显示没有太严苛的要求的话,建议还是使用预定义的对话框,无论从功能还是容错机..._位于tkinter模块中的子模块___ 、___ 、___ 和___ ,包括通用 的预定义对话框;用户

【OpenCV】初识OpenCV(简介、windows下安装及其开发部署)_windows安装opencv-程序员宅基地

文章浏览阅读7k次,点赞9次,收藏65次。详细介绍了OpenCV及其在windows编译环境中的详细安装部署_windows安装opencv

端口和适配器架构——DDD好帮手_端口适配器架构 代码-程序员宅基地

文章浏览阅读860次。摘要本文源自2018领域驱动设计中国峰会《领域驱动设计与演进式架构专题》的Session之一,是其博客版在实践领域驱动设计时,可以挑选一些方法互为参照,端口和适配器架构概念简单,容易掌握,适合作为实践领域驱动设计的辅助方法。大概一个月前,在做2018年领域驱动设计大会预告的时候,上一届大会的主题演讲者肖然提出这样的担忧:工具和方法似乎没有很好地解决“落地难”的挑战没有一套方法能够打遍..._端口适配器架构 代码

随便推点

爬取唐诗-程序员宅基地

文章浏览阅读843次。首先我们打开唐诗三百首网页1 http://www.gushiwen.org/gushi/tangshi.aspx目标分析:1、爬取网页七大板块:五言绝句,七言绝句,五言律诗,七言律诗,五言古诗,七言古诗,乐府。2、爬取每个板块的所有古诗。3、爬取每个古诗词内容。网页详情如下:我们很容易就能发现,每一个分类都是包裹在:1 <div i..._获取唐诗三百首接口

Laravel学习:请求到响应的生命周期-程序员宅基地

文章浏览阅读93次。Laravel请求到响应的整个执行过程,主要可以归纳为四个阶段,即程序启动准备阶段、请求实例化阶段、请求处理阶段、响应发送和程序终止阶段。程序启动准备阶段服务容器实例化服务容器的实例化和基本注册,包括了服务容器本身注册、基础服务提供者注册、核心类别名注册和应用的基本路径注册。注册的服务只是具体的类名,是通过反射机制来实例化对象,并且..._laravel new client() 响应时长

思科 下一跳_二层交换机下一跳命令-程序员宅基地

文章浏览阅读3.1k次,点赞2次,收藏6次。命令如下 仅供参考A :Router>enable Router#conf terminal Enter configuration commands, one per line. End with CNTL/Z.Router(config)#interface gigabitEthernet 0/0Router(config-if)#ip address 192.168.1..._二层交换机下一跳命令

IFeatureClass接口_list<ifeatureclass>-程序员宅基地

文章浏览阅读3.7k次。IFeatureClass用于访问控制要素类行为和属性的成员IFeatureClass接口是获取和设置要素类属性的主要接口。例如,使用IFeatureClass接口获取要素类类型、获取满足查询条件的要素数目或在要素类中创建新要素。IFeatureClass接口继承了IObjectClass接口。成员AddField 向这个类中添加一个字段。AddIndex _list

利用Mysql into outfile给网站留后门-程序员宅基地

文章浏览阅读9.6k次。Mysql into outfile使用Mysql into outfile语句,可以方便导出表格的数据。同样也可以生成某些文件。因此有些人会利用sql注入生成特定代码的文件,然后执行这些文件。将会造成严重的后果。Mysql into outfile 生成PHP文件SELECT 0x3C3F7068702073797374656D28245F524551554553545B636D645D293B3

商业智能软件对比评测: FineBI 和 Tableau -程序员宅基地

文章浏览阅读358次。FineBI和Tableau是比较好的自助式商业智能软件,功能都很强大,是企业数据可视化不可或缺的利器,但两款产品还是有非常大的区别的,例如Tableau的功能全面且深入,更适合专业的数据分析人员,而FineBI则是面向普通的业务人员,数据分析过程更人性化,更简单和易用,并为企业提供了全面的数据管理和用户管理策略。下面对这两款商业智能软件做个对比评测。一、产品理念FineBI是帆软公司推出的自助..._centos7安装finebi

推荐文章

热门文章

相关标签