洛谷P3704 [SDOI2017]数字表格

题目描述

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

f[0]=0f[0]=0 ,f[1]=1f[1]=1 ,

f[n]=f[n-1]+f[n-2],n\geq 2f[n]=f[n−1]+f[n−2],n≥2

Doris用老师的超级计算机生成了一个n×mn×m 的表格,

第ii 行第jj 列的格子中的数是f[\gcd(i,j)]f[gcd(i,j)] ,其中\gcd(i,j)gcd(i,j) 表示i,ji,j 的最大公约数。

Doris的表格中共有n×mn×m 个数,她想知道这些数的乘积是多少。

答案对10^9+7109+7 取模。

输入输出格式

输入格式:

有多组测试数据。

第一个一个数TT ,表示数据组数。

接下来TT 行,每行两个数n,mn,m

输出格式:

输出TT 行,第ii 行的数是第ii 组数据的结果

输入输出样例

输入样例#1:

3
2 3
4 5
6 7

输出样例#1:

1
6
960

说明

对10\%10% 的数据,1\leq n,m\leq 1001≤n,m≤100

对30\%30% 的数据,1\leq n,m\leq 10001≤n,m≤1000

另外存在30\%30% 的数据,T\leq 3T≤3

对100\%100% 的数据,T\leq1000,1\leq n,m\leq 10^6T≤1000,1≤n,m≤106

时间限制:5s

内存限制:128MB

一道明年也做不出来的反演题,。

参考了一下洛谷题解

$$\prod_{d=1}^n\prod_{i=1}^n\prod_{j=1}^mif(gcd(i,j)==d)f[gcd(i,j)]$$ $$\prod_{d=1}^{n}f[d]^{\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[gcd(i,j)==1]}$$

观察上面的$$\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[gcd(i,j)==1]$$

这是一个经典反演问题,它等价于

$$\sum_{i=1}^{n/d}\mu(i)[\frac{n}{id}][\frac{m}{id}]$$

令$T=id$

$$\prod_{T=1}^{n}\prod_{d|T}f[d]^{[n/T][m/T]\mu(T/d)}$$

$$\prod_{T=1}^{n}(\prod_{d|T}f[d]^{\mu(T/d)})^{[n/T][m/T]}$$

然后对于$[n/T]$和$[m/T]$分块

里面的那一个直接暴力,

不明白为什么最后要%mod-1QWQ...

// luogu-judger-enable-o2
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int mod=1e9+7;
const int MAXN=1e6;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int fastpow(int a,int p)
{
    int base=1;
    while(p)
    {
        if(p&1) base=1LL*base%mod*a%mod;
        a=1LL*a%mod*a%mod%mod;
        p>>=1;
    }
    return base%mod;
}
int mu[MAXN+10],sum[MAXN+10],fib[MAXN+10],nfib[MAXN+10],vis[MAXN+10],prime[MAXN],tot;
void Pre()
{
    fib[1]=1;
    for(int i=2;i<=MAXN;i++) fib[i]=(fib[i-1]%mod+fib[i-2]%mod)%mod;
    for(int i=1;i<=MAXN;i++) 
        nfib[i]=(fastpow(fib[i],mod-2)+mod)%mod;
    vis[1]=1;mu[1]=1;
    for(int i=2;i<=MAXN;i++)
    {
        if(!vis[i]) prime[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot&&i*prime[j]<=MAXN;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) {mu[i*prime[j]]=0;break;}
            else mu[i*prime[j]]=-mu[i];
        }
    }
    fill(sum,sum+MAXN,1);
    for(int i=1;i<=MAXN;i++)
    {
        if(mu[i]==0) continue;
        for(int j=i;j<=MAXN;j+=i)
        {
            if(mu[i]==-1) sum[j]=1ll*sum[j]%mod*nfib[j/i]%mod;
            if(mu[i]==1)  sum[j]=1ll*sum[j]%mod*fib[j/i]%mod;
        }
    }
    for(int i=1;i<=MAXN;i++) sum[i]=1ll*sum[i-1]*sum[i]%mod;
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #endif
    Pre();    
    int QWQ=read();
    while(QWQ--)
    {
        int N=read(),M=read();
        if(N>M) swap(N,M);
        long long int ans=1;
        for(int i=1,nxt;i<=N;i=nxt+1)
        {
            nxt=min(N/(N/i),M/(M/i));
            long long int pw=1ll*sum[nxt]*fastpow(sum[i-1],mod-2)%mod;
            ans=(1ll*ans*(fastpow(pw,1ll*(N/i)*(M/i)%(mod-1))))%mod;
        }
        printf("%lld\n",(ans+mod)%mod);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏calmound

HDU 2011 菜鸟杯

A:该题写了很久,一直TLE,主要是枚举到n/2时间复杂度实在太高了,其实嘛,这道题就是因式分解,所以就是i*i=n,也就是sqrt(n) #include<s...

31740
来自专栏小樱的经验随笔

1082 与7无关的数(思维题,巨坑)

1082 与7无关的数 题目来源:                 有道难题 基准时间限制:1 秒 空间限制:131072 KB 分值: 5        ...

34570
来自专栏鸿的学习笔记

写给开发者的机器学习指南(十)

An attempt at rank prediction for topselling books using text regression

9830
来自专栏数据结构与算法

cf567E. President and Roads(最短路计数)

首先确定哪些边一定在最短路上,一个条件是 从起点到该点的最短路 + 边权 + 从该点到终点的最短路 = 从起点到终点的最短路

11820
来自专栏数据结构与算法

1893. [国家集训队2011]等差子序列(bitset)

★★   输入文件:nt2011_sequence.in   输出文件:nt2011_sequence.out 简单对比 时间限制:0.3 s   内存限制:5...

355100
来自专栏应兆康的专栏

100个Numpy练习【4】

Numpy是Python做数据分析必须掌握的基础库之一,非常适合刚学习完Numpy基础的同学,完成以下习题可以帮助你更好的掌握这个基础库。

781120
来自专栏小樱的经验随笔

Codeforces Round #412 (rated, Div. 2, base on VK Cup 2017 Round 3)(A.B.C,3道暴力题,C可二分求解)

A. Is it rated? time limit per test:2 seconds memory limit per test:256 megabyte...

37870
来自专栏calmound

poj 3126 Prime Path (广搜)

http://poj.org/problem?id=3126 题意:从一个素数,挨个数位的变换,在此过程中保证每次变换的数位都是素数,最后变到所给的另一个素数最...

30850
来自专栏owent

C++ 新特性学习(六) — 新的字符串编码和伪随机数

使用u””为能至少储存UTF-16的16位元编码,对应’\u’表示16位元的字符。

9410
来自专栏xingoo, 一个梦想做发明家的程序员

回溯法算法框架

回溯法:有通用解题法 之称,可以系统的搜索一个问题的所有解和任一解,是一个既带有系统性,又带有跳跃性的搜索算法。 算法基本思想:   确定解空间后   从开始节...

35560

扫码关注云+社区

领取腾讯云代金券